A note on the NP-hardness of two matching problems in induced subgridsy
Discrete Mathematics and Theoretical Computer Science, cilt.15, sa.2, ss.233-242, 2013 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 15 Sayı: 2
- Basım Tarihi: 2013
- Dergi Adı: Discrete Mathematics and Theoretical Computer Science
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.233-242
- Anahtar Kelimeler: Edge dominating set, Grid graphs, Maximum induced matching, Minimum maximal matching
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out some promising research directions. We also sketch the general framework of a unified approach to show the NP-hardness of some problems in subgrids.