Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
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 fo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2336 |
| _version_ | 1797725565269049344 |
|---|---|
| author | Brandstädt Andreas Mosca Raffaele |
| author_facet | Brandstädt Andreas Mosca Raffaele |
| author_sort | Brandstädt Andreas |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T10:33:05Z |
| format | Article |
| id | doaj.art-d2d5f041c1a6487f904f0142b218fcd4 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T10:33:05Z |
| publishDate | 2022-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-d2d5f041c1a6487f904f0142b218fcd42023-09-02T09:07:26ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-11-014241139116210.7151/dmgt.2336Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial TimeBrandstädt Andreas0Mosca Raffaele1Institut für Informatik, Universität Rostock, A.-Einstein-Str. 22, D-18051 Rostock, GermanyDipartimento di Economia, Universitá degli Studi “G. D’Annunzio”, Pescara65121, ItalyLet 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.https://doi.org/10.7151/dmgt.2336dominating induced matchingp9-free graphspolynomial time algorithm05c6968r10 |
| spellingShingle | Brandstädt Andreas Mosca Raffaele Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time Discussiones Mathematicae Graph Theory dominating induced matching p9-free graphs polynomial time algorithm 05c69 68r10 |
| title | Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time |
| title_full | Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time |
| title_fullStr | Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time |
| title_full_unstemmed | Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time |
| title_short | Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time |
| title_sort | finding dominating induced matchings in p9 free graphs in polynomial time |
| topic | dominating induced matching p9-free graphs polynomial time algorithm 05c69 68r10 |
| url | https://doi.org/10.7151/dmgt.2336 |
| work_keys_str_mv | AT brandstadtandreas findingdominatinginducedmatchingsinp9freegraphsinpolynomialtime AT moscaraffaele findingdominatinginducedmatchingsinp9freegraphsinpolynomialtime |