1. bookVolume 42 (2022): Edition 4 (November 2022)
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
access type Accès libre

Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time

Publié en ligne: 12 Jul 2022
Volume & Edition: Volume 42 (2022) - Edition 4 (November 2022)
Pages: 1139 - 1162
Reçu: 07 Oct 2019
Accepté: 13 May 2020
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
Abstract

Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is 𝕅𝕇-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P7-free graphs and in polynomial time for P8-free graphs. In this paper, we solve it in polynomial time for P9-free graphs.

Keywords

MSC 2010

[1] G. Bacsó and Zs. Tuza, A characterization of graphs without long induced paths, J. Graph Theory 14 (1990) 455–464. https://doi.org/10.1002/jgt.3190140409 Search in Google Scholar

[2] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 289–296. https://doi.org/10.1016/0095-8956(73)90042-7 Search in Google Scholar

[3] A. Brandstädt, C. Hundt and R. Nevries, Efficient edge domination on hole-free graphs in polynomial time, Conference Proceedings LATIN 2010, Lecture Notes in Comput. Sci. 6034 (2010) 650–661. https://doi.org/10.1007/978-3-642-12200-2_56 Search in Google Scholar

[4] A. Brandstädt and R. Mosca, Dominating induced matchings for P7-free graphs in linear time, Algorithmica 68 (2014) 998–1018. https://doi.org/10.1007/s00453-012-9709-4 Search in Google Scholar

[5] A. Brandstädt and R. Mosca, Finding dominating induced matchings in P8-free graphs in polynomial time, Algorithmica 77 (2017) 1283–1302. https://doi.org/10.1007/s00453-016-0150-y Search in Google Scholar

[6] A. Brandstädt and R. Mosca, Dominating induced matchings in S1,2,4-free graphs, Discrete Appl. Math. 278 (2020) 83–92. https://doi.org/10.1016/j.dam.2018.09.028 Search in Google Scholar

[7] A. Brandstädt and R. Mosca, Finding dominating induced matchings in S2,2,3-free graphs, Discrete Appl. Math. 283 (2020) 417–434. https://doi.org/10.1016/j.dam.2020.01.028 Search in Google Scholar

[8] A. Brandstädt and R. Mosca, Finding dominating induced matchings in S1,1,5-free graphs, Discrete Appl. Math. 284 (2020) 269–280. https://doi.org/10.1016/j.dam.2020.03.043 Search in Google Scholar

[9] D.M. Cardoso, N. Korpelainen and V.V. Lozin, On the complexity of the dominating induced matching problem in hereditary classes of graphs, Discrete Appl. Math. 159 (2011) 521–531. https://doi.org/10.1016/j.dam.2010.03.011 Search in Google Scholar

[10] D.L. Grinstead, P.L. Slater, N.A. Sherwani and N.D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (1993) 221–228. https://doi.org/10.1016/0020-0190(93)90084-M Search in Google Scholar

[11] A. Hertz, V.V. Lozin, B. Ries, V. Zamaraev and D. de Werra, Dominating induced matchings in graphs containing no long claw, J. Graph Theory 88 (2018) 18–39. https://doi.org/10.1002/jgt.22182 Search in Google Scholar

[12] N. Korpelainen, V.V. Lozin and C. Purcell, Dominating induced matchings in graphs without a skew star, J. Discrete Algorithms 26 (2014) 45–55. https://doi.org/10.1016/j.jda.2013.11.002 Search in Google Scholar

[13] C.L. Lu, M.-T. Ko and C.Y. Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Appl. Math. 119 (2002) 227–250. https://doi.org/10.1016/S0166-218X(01)00198-6 Search in Google Scholar

[14] C.L. Lu and C.Y. Tang, Solving the weighted efficient edge domination problem on bipartite permutation graphs, Discrete Appl. Math. 87 (1998) 203–211. https://doi.org/10.1016/S0166-218X(98)00057-2 Search in Google Scholar

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo