Faster Scaling Algorithms for General Graph Matching Problems
Report ID: TR-222-89Author: Tarjan, Robert E. / Gabow, Harold N.
Date: 1989-04-00
Pages: 50
Download Formats: |PDF|
Abstract:
This paper presents an algorithm for minimum cost matching on a general graph with integral edge costs, that runs in time close to the best known bound for cardinality matching. ... Other applications of the new algorithm are given, including an efficient implementation of Christofides' travelling salesman approximation algorithm and efficient solutions to update problems that require the linear programming duals for matching.