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

DOI10.1016/0167-6377(84)90068-3MaRDI QIDQ792885zbMATHOpenAlexFDO

Authors 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

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

Recommendations

• A linear time algorithm for maximum matchings in convex, bipartite graphs
• An efficient algorithm for the bipartite matching problem
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• scientific article; zbMATH DE number 1305475
• On the computational complexity of the bipartizing matching problem
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
• Approximation algorithms for bipartite matching with metric and geometric costs
• A near-linear time ε-approximation algorithm for geometric bipartite matching

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Maximum matching in a convex bipartite graph

Cited in

(12)

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

This page was built for publication: An 0(n log n) algorithm for the convex bipartite matching problem

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