Computing maximum non-crossing matching in convex bipartite graphs

DOI10.1016/j.dam.2015.02.014zbMath1315.05108OpenAlexW1968325900MaRDI QIDQ2348053

Xiaomin Liu, Haitao Wang, Danny Z. Chen

Publication date: 10 June 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.02.014

zbMATH Keywords

algorithmsdata structuresmaximum matchingconvex bipartite graphsmaximum non-crossing matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Data structures (68P05)

Related Items (2)

Strongly stable and maximum weakly stable noncrossing matchings ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• On computing the length of longest increasing subsequences
• Efficient labelling algorithms for the maximum noncrossing matching problem
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Network Flow and Testing Graph Connectivity
• Design and implementation of an efficient priority queue
• Paths, Trees, and Flowers
• Maximum matching in a convex bipartite graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Computing maximum non-crossing matching in convex bipartite graphs