Faster Scaling Algorithms for General Graph Matching Problems

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.