An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs

DOI10.1016/S0020-0190(00)00101-0zbMath1003.68108OpenAlexW2095026547MaRDI QIDQ1607053

K. V. R. C. N. Kishore, Sanjeev Saxena

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00101-0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• An improvement on parallel computation of a maximal matching
• Deterministic parallel list ranking
• An improved parallel algorithm for maximal matching
• An optimal parallel algorithm for maximal matching
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Fast Derandomization Scheme and Its Applications

This page was built for publication: An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs