- Tytuł:
- Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
- Autorzy:
-
Brandstädt, Andreas
Mosca, Raffaele - Powiązania:
- https://bibliotekanauki.pl/articles/32222548.pdf
- Data publikacji:
- 2022-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
dominating induced matching
P 9 -free graphs
polynomial time algorithm - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1139-1162
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł