OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS

DOI10.1080/10637199708915615zbMATH Open0873.68087OpenAlexW2002533383MaRDI QIDQ3130156FDOQ3130156

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• Optimal merging and sorting on the EREW PRAM
• Efficient parallel algorithms for bipartite permutation graphs

Cited In (4)

• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Efficient parallel algorithms for bipartite permutation 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)