Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs

DOI10.1016/j.tcs.2019.10.042zbMath1436.68260OpenAlexW2989478260WikidataQ126834987 ScholiaQ126834987MaRDI QIDQ2283031

Yanyan Li

Publication date: 27 December 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.10.042

zbMATH Keywords

graph matchingconvex bipartite graphscoarse grained parallel computinglinear-time Hamiltonian circuit

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Cites Work

• Unnamed Item
• An 0(n log n) algorithm for the convex bipartite matching problem
• Algorithms for maximum independent set in convex bipartite graphs
• A linear-time algorithm for a special case of disjoint set union
• Some parallel algorithms on interval graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Parallel maximum independent set in convex bipartite graphs
• Finding maximum edge bicliques in convex bipartite graphs
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• HAMILTONian circuits in chordal bipartite graphs
• Dynamic Matchings in Convex Bipartite Graphs
• Maximum Edge Bicliques in Tree Convex Bipartite Graphs
• Parallel computation on interval graphs: algorithms and experiments
• Maximum matching in a convex bipartite graph

This page was built for publication: Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs