Decomposition algorithms for solving the minimum weight maximal matching problem
Networks, cilt.62, sa.4, ss.273-287, 2013 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 62 Sayı: 4
- Basım Tarihi: 2013
- Doi Numarası: 10.1002/net.21516
- Dergi Adı: Networks
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.273-287
- Anahtar Kelimeler: Benders decomposition, Gallai-Edmonds decomposition, minimum maximal matching, mixed integer programming, vertex cover
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Abstract- 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 Wiley Periodicals, Inc. NETWORKS, Vol. 62(4), 273-287 2013 Copyright © 2013 Wiley Periodicals, Inc.