Hardness and approximation of minimum maximal matchings
International Journal of Computer Mathematics, cilt.91, sa.8, ss.1635-1654, 2014 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 91 Sayı: 8
- Basım Tarihi: 2014
- Doi Numarası: 10.1080/00207160.2013.853052
- Dergi Adı: International Journal of Computer Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.1635-1654
- Anahtar Kelimeler: edge dominating set, graph algorithms, minimum maximal matching, regular graphs; NP-completeness and approximation
- Boğaziçi Üniversitesi Adresli: Evet
Özet
In this paper, we consider the minimum maximal matching problem in some classes of graphs such as regular graphs. We show that the minimum maximal matching problem is NP-hard even in regular bipartite graphs, and a polynomial time exact algorithm is given for almost complete regular bipartite graphs. From the approximation point of view, it is well known that any maximal matching guarantees the approximation ratio of 2 but surprisingly very few improvements have been obtained. In this paper we give improved approximation ratios for several classes of graphs. For example any algorithm is shown to guarantee an approximation ratio of (2-o(1)) in graphs with high average degree. We also propose an algorithm guaranteeing for any graph of maximum degree Δ an approximation ratio of (2−1/Δ), which slightly improves the best known results. In addition, we analyse a natural linear-time greedy algorithm guaranteeing a ratio of (2−23/18k) in k-regular graphs admitting a perfect matching.