Decomposition Algorithms for Solving the Minimum Weight Maximal Matching Problem

作者：Bodur Merve; Ekim Tinaz; Taskin Z Caner^*

来源：Networks, 2013, 62(4): 273-287.

DOI：10.1002/net.21516

• minimum maximal matching
• vertex cover
• mixed integer programming
• Benders decomposition
• Gallai-Edmonds decomposition

- We investigate the problem of finding a maximal matching that has minimum total weight on a given edge-weighted graph. Although the minimum weight maximal matching problem is NP-hard in general, polynomial time exact or approximation algorithms on several restricted graph classes are given in the literature. In this article, we propose an exact algorithm for solving several variants of the problem on general graphs. In particular, we develop integer programming (IP) formulations for the problem and devise a decomposition algorithm, which is based on a combination of IP techniques and combinatorial matching algorithms. Our computational tests on a large suite of randomly generated graphs show that our decomposition approach significantly improves the solvability of the problem compared to the underlying IP formulation.

• 出版日期2013-12