zbMATH — the first resource for mathematics

Sorting in one round. (English) Zbl 0461.05039

05C35 Extremal problems in graph theory
05C20 Directed graphs (digraphs), tournaments
68P10 Searching and sorting
Full Text: DOI
[1] K. E. Batcher,Sorting networks and their applications, Notices Amer. Math. Soc.14 (1967), 283.
[2] B. Bollobás,Extremal Graph Theory, London Math. Soc. Monographs, Vol. 11, Academic Press, London-New York-San Francisco, 1978.
[3] B. BollobásGraph Theory – An Introductory Course, Graduate Texts in Maths.63, Springer-Verlag, New York-Heidelberg, 1979.
[4] P. Erdös and A. Rényi,On a problem in the theory of graphs, Publ. Math. Inst. Hungar. Acad. Sci.7 (1962), 215–235 (in Hungarian).
[5] R. W. Floyd and D. E. Knuth,The Bose-Nelson sorting problem, a survey of combinatorial theory (Srivastava et al., eds.), North-Holland Publ. Co., 1973, pp. 163–172. · Zbl 0259.05005
[6] Roland Häggkvist and Pavol Hell,Parallel sorting with constant time for comparisons, SIAM J. Comput., to appear. · Zbl 0461.68062
[7] D. E. Knuth,The Art of Computer Programming, Vol. 3,Sorting and Searching, Addison-Wesley, Reading, Mass., 1973. · Zbl 0191.17903
[8] D. Van Voorhis,An Improved Lower Bound for the Bose-Nelson Sorting Problem, Technical Report No. 7, Digital Systems Laboratory, Stanford University, 1971.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.