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

DOI10.1287/IJOC.7.3.298MaRDI QIDQ4896435zbMATHOpenAlexFDO

Authors Donald L. Miller, Joseph F. Pekny

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)

Recommendations

• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
• A polynomial algorithm for b-matchings: An alternative approach
• A new algorithm for general matching problems using network flow subproblems
• scientific article; zbMATH DE number 515943

Cited in

(10)

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

Describes a project that uses

Uses Software

• TSPLIB

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

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