A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities

DOI10.1287/IJOC.7.3.298zbMath0859.90116OpenAlexW2131075792MaRDI QIDQ4896435

Joseph F. Pekny, Donald L. Miller

Publication date: 20 October 1996

Published in: ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.7.3.298

zbMATH Keywords

weighted undirected graphfrozen superverticesminimum cost perfect \(b\)-matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (10)

Exact and heuristic algorithms for the Hamiltonian \(p\)-median problem ⋮ Traveling salesman problem heuristics: leading methods, implementations and latest advances ⋮ A 0.5358-approximation for Bandpass-2 ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ The Cutting Plane Method is Polynomial for Perfect Matchings ⋮ A genetic-based framework for solving (multi-criteria) weighted matching problems. ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Efficient Approximation Algorithms for Weighted $b$-Matching ⋮ Fast algorithms for the undirected negative cost cycle detection problem

Uses Software

• Unnamed Item

This page was built for publication: A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities