Geodesic
Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1139-1162

Voir la notice de l'article provenant de la source Library of Science

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: dominating induced matching, P 9 -free graphs, polynomial time algorithm 
@article{DMGT_2022_42_4_a8,
     author = {Brandst\"adt, Andreas and Mosca, Raffaele},
     title = {Finding {Dominating} {Induced} {Matchings} in {P\protect\textsubscript{9}-Free} {Graphs} in {Polynomial} {Time}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1139--1162},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/}
}
TY  - JOUR
AU  - Brandstädt, Andreas
AU  - Mosca, Raffaele
TI  - Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1139
EP  - 1162
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/
LA  - en
ID  - DMGT_2022_42_4_a8
ER  - 
%0 Journal Article
%A Brandstädt, Andreas
%A Mosca, Raffaele
%T Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1139-1162
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/
%G en
%F DMGT_2022_42_4_a8
Brandstädt, Andreas; Mosca, Raffaele. Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1139-1162. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a8/