×

Quasi-monotonic sequences: Theory, algorithms and applications. (English) Zbl 0692.06011

Summary: We present a simple algebraic theory which allows us to solve a variety of combinatorial problems, including the problem of finding convex hulls in two dimensions, the “Trip Around the Moon” problem, a version of the ballot problem, and the problem of enumerating and randomly generating ordered trees of a given size. Individual problems are solved by applying general algorithms and theorems developed within this algebraic theory.

MSC:

06F99 Ordered structures
05A99 Enumerative combinatorics
68R99 Discrete mathematics in relation to computer science
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
68Q25 Analysis of algorithms and problem complexity
52A10 Convex sets in \(2\) dimensions (including convex curves)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A.; Hopcroft, J.; Ullman, J., The design and analysis of computer algorithms, (1975) · Zbl 0326.68005
[2] Andrew, A. M., Another efficient algorithm for convex hulls in two dimensions, Inform. Process. Lett., 9, 216, (1979) · Zbl 0423.68032 · doi:10.1016/0020-0190(79)90072-3
[3] Bentley, J.; Shamos, M., Divide and conquer for linear expected time, Information Processing Lett., 7, 87, (1978) · Zbl 0404.68046 · doi:10.1016/0020-0190(78)90051-0
[4] Bertrand, J., Solution d’un probleme, Comptes Rendus des Seances de l’Academie des Sciences, 105, 369, (1887) · JFM 19.0200.03
[5] Dershowitz, Nachum; Zaks, Shmuel, Enumerations of ordered trees, Discrete Math., 31, 9, (1980) · Zbl 0443.05049 · doi:10.1016/0012-365X(80)90168-5
[6] Dolev, Danny; Klawe, Maria; Rodeh, Michael, An \(O(n\log n)\) unidirectional distributed algorithm for extrema finding in a circle, J. Algorithms, 3, 245, (1982) · Zbl 0493.68074
[7] Duval, J. P., Factorizing words over an ordered alphabet, J. Algorithms, 4, 363, (1983) · Zbl 0532.68061
[8] Dvornicich, Roberto, On a problem of cyclic permutations of integers, Discrete Appl. Math., 2, 353, (1980) · Zbl 0444.05003 · doi:10.1016/0166-218X(80)90032-3
[9] Gardner, M., Catalan numbers: an integer sequence that materializes in unexpected places, Scientific American, 243, 120, (1976)
[10] Gould, H. W., Research bibliography of two special number sequences, (1976) · Zbl 0327.10001
[11] Graham, R. L., A combinatorial theorem for partial sums, Ann. Math. Statist, 34, 1600, (1963) · Zbl 0121.13404
[12] personal communication
[13] Lothaire, M., Combinatorics on words, (1983) · Zbl 0514.20045
[14] Meijer, H.; Akl, S., The design and analysis of a new hybrid sorting algorithm, Inform. Process. Lett., 10, 213, (1980) · Zbl 0447.68067 · doi:10.1016/0020-0190(80)90143-X
[15] Preparata, F. P., An optimal real-time algorithm for planar convex hulls, Comm. ACM, 22, 402, (1979) · Zbl 0404.68069 · doi:10.1145/359131.359132
[16] Read, RonaldC.; Read, R. C., The coding of various kinds of unlabeled trees, Graph theory and computing, 153, (1972), Academic Press, New York · Zbl 0247.05104
[17] Sands, A. D., On generalised Catalan numbers, Discrete Math., 21, 219, (1978) · Zbl 0404.05006 · doi:10.1016/0012-365X(78)90094-8
[18] Silberger, D. M., Occurrences of the integer \((2n-2)!/n!(n-1)!\), Prace Mat., 13, 91, (1969) · Zbl 0251.05005
[19] Singmaster, David, An elementary evaluation of the Catalan numbers, Amer. Math. Monthly, 85, 366, (1978) · Zbl 0406.05002
[20] Singmaster, David, Some Catalan correspondences, J. London Math. Soc. (2), 19, 203, (1979) · Zbl 0394.05002
[21] Spitzer, Frank, A combinatorial lemma and its application to probability theory, Trans. Amer. Math. Soc., 82, 323, (1956) · Zbl 0071.13003
[22] Srinivasan, R., On some results of takács in ballot problems, Discrete Math., 28, 213, (1979) · Zbl 0413.60006 · doi:10.1016/0012-365X(79)90100-6
[23] Takacs, L., Combinatorial methods in the theory of stochastic processes, (1967) · Zbl 0162.21303
[24] Takacs, L., Ballot problems, Z. Wahrscheinlichkeitstheorie Verw. Gebiete, 1, 154, (1962) · Zbl 0114.33804
[25] Viennot, Gérard, Algèbres de Lie libres et monoïdes libres, (1978) · Zbl 0114.33804
[26] Yao, A., A lower bound to finding convex hulls, J. Assoc. Comput. Mach., 28, 780, (1981) · Zbl 0468.68080 · doi:10.1145/322276.322289
[27] Zaks, S.; Richards, D., Generating trees and other combinatorial objects lexicographically, SIAM J. Comput., 8, 73, (1979) · Zbl 0406.05026 · doi:10.1137/0208006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.