A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph

DOI10.1287/IJOC.6.1.68zbMath0798.90128OpenAlexW2041801439MaRDI QIDQ4291501

Joseph F. Pekny, Donald L. Miller

Publication date: 10 May 1994

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

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

zbMATH Keywords

network flow algorithmweighted undirected graphminimum cost perfect two-matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Large-scale problems in mathematical programming (90C06)

Related Items (12)

A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program ⋮ A bound for the symmetric travelling salesman problem through matroid formulation ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ Approximation algorithms for some vehicle routing problems ⋮ Estimation-based metaheuristics for the probabilistic traveling salesman problem ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ An approximation algorithm for maximum triangle packing ⋮ Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem ⋮ Lower bounding techniques for frequency assignment ⋮ A \(\frac78\)-approximation algorithm for metric Max TSP ⋮ Generation of lower bounds for minimum span frequency assignment ⋮ Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers

Uses Software

• Unnamed Item

This page was built for publication: A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph