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

DOI10.1287/IJOC.7.3.298zbMATH Open0859.90116OpenAlexW2131075792MaRDI QIDQ4896435FDOQ4896435

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cited In (10)

• Fast algorithms for the undirected negative cost cycle detection problem
• 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
• Approximation algorithms in combinatorial scientific computing
• Exact and heuristic algorithms for the Hamiltonian \(p\)-median problem
• Traveling salesman problem heuristics: leading methods, implementations and latest advances
• A genetic-based framework for solving (multi-criteria) weighted matching problems.
• The cutting plane method is polynomial for perfect matchings
• A 0.5358-approximation for Bandpass-2
• Efficient approximation algorithms for weighted \(b\)-matching

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)