Minimum maximal matching is np-hard in regular bipartite graphs
5th International Conference on Theory and Applications of Models of Computation, TAMC 2008, Xian, Çin, 25 - 29 Nisan 2008, cilt.4978 LNCS, ss.364-374, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Cilt numarası: 4978 LNCS
- Doi Numarası: 10.1007/978-3-540-79228-4_32
- Basıldığı Şehir: Xian
- Basıldığı Ülke: Çin
- Sayfa Sayıları: ss.364-374
- Anahtar Kelimeler: Minimum Maximal Matching, Regular bipartite graphs, Stable marriage, Unmatched pairs
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Yannakakis and Gavril showed in [10] that the problem of finding a maximal matching of minimum size (MMM for short), also called Minimum Edge Dominating Set, is NP-hard in bipartite graphs of maximum degree 3 or planar graphs of maximum degree 3. Horton and Kilakos extended this result to planar bipartite graphs and planar cubic graphs [6]. Here, we extend the result of Yannakakis and Gavril in [10] by showing that MMM is NP-hard in the class of k-regular bipartite graphs for all k≤3 fixed. © 2008 Springer-Verlag Berlin Heidelberg.