|
 ABSTRACT
Examples of fruitful interaction between geometrical combinatorics and the design and analysis of algorithms are presented. A demonstration is given of the way in which a simple geometrical construction yields new and efficient algorithms for various searching and list manipulation problems.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
|
| |
3
|
Comtet, L. Advanced Combinatorics. D. Reided Pub. Co., Boston, Mass., 1974.
|
| |
4
|
Burge, W.H. An analysis of a tree sorting method and some properties of a set of trees. In Proc. 1st USA-Japan Comptr. Conf., 1972, pp. 372-378.
|
| |
5
|
Flajolet, P., Franfon, J., Viennot, G., and Vuillemin, J. Algorithmique et combinatoire des arbres et permutations. To appear (1981).
|
| |
6
|
Flajolet, P., Frangon, J., and Vuillemin, J. Sequence of operation analysis for dynamic data structures. 3". Algorithms. To appear (1980).
|
| |
7
|
Foata, D., and Schutzenberger, M.P. Theorie g~omCtrique des polynCmes Euleriens. Lecture Notes in Mathematics, No. 138, Springer-Verlag, Berlin, 1970.
|
| |
8
|
Foata, D., and Strehl, V. Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers. Math. Zamet. 137 (1974), 256-264.
|
| |
9
|
Frangan, J. Arbres binaires de recherche, propriCtCs combinatoires et applications. RA I R O I n f ormatique Thdorique 10 (1976), 35-50.
|
| |
10
|
Frangan, J., Viennot, G., and VuiUemin, J. Description et analyse d'une reprCsentation pefformante des files de prioritC. Rep. 12, Lab. d'Informatique, Orsay, France; also in Proc. 19th Ann. ACM Syrup. on Foundations of Comptr. Sci., 1978, pp. 1-7.
|
| |
11
|
Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States
[doi> 10.1145/800105.803395]
|
| |
12
|
Hoare, C.A.R. Quicksort. Comptr. J. 5, 1 (1962), 10--15.
|
| |
13
|
|
| |
14
|
Sedgewick, R. Quicksort. Rep. STAN-CS-75-492, Dept. Comptr. Sci., Stanford Univ., Stanford, Calif,, May 1975.
|
| |
15
|
Stephenson, C.J. A method for constructing binary search trees by making insertions at the root. Rep. RC 6298, IBM Thomas J. Watson Res. Ctr., Yorktown Heights, N.Y., 1976.
|
| |
16
|
Viennot, G. Quelques algorithmes de permutations. AstCrique 38-39, Societ6 MathCmatique de France, 1976, pp. 275-293.
|
CITED BY 22
|
|
|
|
|
|
|
|
O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stephen Alstrup , Cyril Gavoille , Haim Kaplan , Theis Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P. Widmayer , Y. F. Wu , C. K. Wong, Distance problems in computational geometry with fixed orientations, Proceedings of the first annual symposium on Computational geometry, p.186-195, June 05-07, 1985, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf