INFORMS Journal on Computing · 1994 · 30 citations · 0 references
ComputingComputer ScienceAlgorithmsOptimizationTheory Of ComputationCombinatorial OptimizationGraph AlgorithmsInteger ProgrammingMatching TheoryNetwork Flow AlgorithmsBipartite MatchingGraph MatchingMatching AlgorithmsMatching ProblemsPrimal-dual Algorithms
We describe an algorithm for finding a minimum cost perfect two-matching in a weighted undirected graph, G = (V, E). The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. First, the degree constrained LP relaxation is posed as a bipartite two-matching problem and solved using a network flow algorithm. Next, the facet inducing two-matching cutset inequalities are activated selectively within a primal-dual framework that progressively eliminates half-integral values from the primal solution while maintaining dual feasibility. The algorithm is guaranteed to terminate in O(|V| 2 |E|) steps, although computational results suggest this upper bound to be pessimistic. The algorithm is experimentally shown to be effective on TSPLIB test problem [1] ranging in size from 17 to 11,849 vertices. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.