Integer programming formulations for the minimum weighted maximal matching problem
Optimization Letters, cilt.6, sa.6, ss.1161-1171, 2012 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 6 Sayı: 6
- Basım Tarihi: 2012
- Doi Numarası: 10.1007/s11590-011-0351-x
- Dergi Adı: Optimization Letters
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.1161-1171
- Anahtar Kelimeler: Edge dominating set, Integer programming, Minimum maximal matching
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement. © 2011 Springer-Verlag.