Solving large‐scale matching problems efficiently: A new primal matching approach
Ulrich Derigs · Networks · 1986
Abstract In this article we introduce a new approach to the weighted matching problem. It is designed specifically for problems defined on large dense graphs. It is a two‐phase approach that first solves a matching problem on a sparse subgraph and then considers the remaining edges in a pricing out/reoptimization phase. Computational experience is reported which documents the efficiency of this algorithm.