OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS

DOI10.1080/10637199708915615MaRDI QIDQ3130156zbMATH OpenOpenAlexFDO

Authors Hiryoung Kim, Alan P. Sprague

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) Distributed algorithms (68W15) Computer system organization (68M99)

Recommendations

• An optimal parallel algorithm for maximal matching
• Finding a maximum matching in a permutation graph
• Finding maximum matching for bipartite graphs in parallel
• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs

Cites work

• scientific article; zbMATH DE number 53193 (Why is no real title available?)
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Efficient parallel algorithms for bipartite permutation graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Optimal merging and sorting on the EREW PRAM

Cited in

(4)

• Efficient parallel algorithms for bipartite permutation graphs
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
• Methods of local optimization for the problem of permutating bipartite graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3130156)