Premium
Solving large‐scale matching problems efficiently: A new primal matching approach
Author(s) -
Derigs Ulrich
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160102
Subject(s) - matching (statistics) , computer science , mathematical optimization , scale (ratio) , algorithm , theoretical computer science , mathematics , statistics , physics , quantum mechanics
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.