An O(n log n log log n) parallel maximum matching algorithm for bipartite graphs

DOI10.1016/0020-0190(87)90193-1zbMath0623.68065OpenAlexW2023428944MaRDI QIDQ1091829

Taenam Kim, Kyung-Yong Chwa

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90193-1

zbMATH Keywords

treecomputational complexitymatchingbipartite graphsparallel algorithmserial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Finding maximum matching for bipartite graphs in parallel, An adjustable linear time parallel algorithm for maximum weight bipartite matching

Cites Work

• Constructing a perfect matching is in random NC
• Parallel concepts in graph theory
• Parallel Matrix and Graph Algorithms
• An O(n2log n) parallel max-flow algorithm
• New Parallel-Sorting Schemes
• Fast parallel sorting algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs