Matching Nuts and Bolts in O(n log n) Time

DOI10.1137/S0895480196304982zbMath0911.68069MaRDI QIDQ4210209

Endre Szemerédi, János Komlós, Yuan Ma

Publication date: 21 September 1998

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

sorting; matching; parallel computation; selection; random graphs; AKS sorting algorithm; bl 871.68100

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68W10: Parallel algorithms in computer science

06A05: Total orders

68W15: Distributed algorithms