OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS

DOI10.1080/10637199708915615zbMath0873.68087OpenAlexW2002533383MaRDI QIDQ3130156

Alan P. Sprague, Hiryoung Kim

Publication date: 22 April 1997

Published in: Parallel Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10637199708915615

zbMATH Keywords

bipartite permutation graphsmaximum matching problemcost-optimal parallel algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68M99) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Optimal merging and sorting on the EREW PRAM
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• On the Complexity of Timetable and Multicommodity Flow Problems
• Efficient parallel algorithms for bipartite permutation graphs

This page was built for publication: OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS