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

DOI10.1016/0167-6377(84)90068-3zbMATH Open0537.90091OpenAlexW2043765170MaRDI QIDQ792885FDOQ792885

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximum matching in a convex bipartite graph
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems

Cited In (12)

• On the domatic number of interval graphs
• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• On Compiling Structured CNFs to OBDDs
• A fast bipartite network flow algorithm for selective assembly
• The maximum deviation just-in-time scheduling problem.
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Bounds and algorithms for geodetic hulls
• On compiling structured CNFs to OBDDs
• 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
• An efficient algorithm for the bipartite matching problem

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)