zbMATH — the first resource for mathematics

Sorting and graphs. (English) Zbl 0579.68041
Graphs and order. The role of graphs in the theory of ordered sets and its applications, Proc. NATO Adv. Study Inst., Banff/Can. 1984, NATO ASI Ser., Ser. C 147, 169-184 (1985).
[For the entire collection see Zbl 0549.00002.]
This interesting paper discusses the number of binary comparisons needed (in a comparison tree model) to sort n elements in k time units. The authors survey in depth most of the many recent results in this area, especially those which deal with the case of fixed k. The results for this case have a highly graph theoretic flavour and the methods used are probabilistic arguments and extremal-graph-theory techniques. We mention one typical result: for every fixed k, the number of comparisons needed to sort n elements in k time units is between \(c_ 1(k)n^{1+1/k}\) and \(c_ 2(k)n^{1+1/k}\log n\).
Reviewer: N.Alon

68P10 Searching and sorting
05C35 Extremal problems in graph theory
68R10 Graph theory (including graph drawing) in computer science
05A15 Exact enumeration problems, generating functions