An 0(n log n) algorithm for the convex bipartite matching problem

DOI10.1016/0167-6377(84)90068-3zbMath0537.90091OpenAlexW2043765170MaRDI QIDQ792885

N. E. Zubov

Publication date: 1984

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90068-3

zbMATH Keywords

convex bipartite graphsbinary heapmaximum cardinality matching problemspecial data structure

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On Compiling Structured CNFs to OBDDs, On the domatic number of interval graphs, A linear time algorithm for maximum matchings in convex, bipartite graphs, On compiling structured CNFs to OBDDs, Bounds and algorithms for geodetic hulls, The maximum deviation just-in-time scheduling problem., Linear-time algorithm for the paired-domination problem in convex bipartite graphs, Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs, A fast bipartite network flow algorithm for selective assembly, Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Maximum matching in a convex bipartite graph
• Unnamed Item
• Unnamed Item