Let G= (V, E) be a finite undirected graph. An edge set 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; this problem is also known as the Efficient Edge Domination problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three and is solvable in linear time for P7-free graphs. However, its complexity was open for Pk-free graphs for any k≥ 8 ; Pk denotes the chordless path with k vertices and k- 1 edges. We show in this paper that the weighted DIM problem is solvable in polynomial time for P8-free graphs. © 2016, Springer Science+Business Media New York.

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

Mosca, Raffaele
2016-01-01

Abstract

Let G= (V, E) be a finite undirected graph. An edge set 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; this problem is also known as the Efficient Edge Domination problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three and is solvable in linear time for P7-free graphs. However, its complexity was open for Pk-free graphs for any k≥ 8 ; Pk denotes the chordless path with k vertices and k- 1 edges. We show in this paper that the weighted DIM problem is solvable in polynomial time for P8-free graphs. © 2016, Springer Science+Business Media New York.
File in questo prodotto:
File Dimensione Formato  
Brandstädt-Mosca2017_Article_FindingDominatingInducedMatchi.pdf

Solo gestori archivio

Descrizione: Article
Tipologia: PDF editoriale
Dimensione 527.81 kB
Formato Adobe PDF
527.81 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
EEDP8fr10rev.pdf

accesso aperto

Tipologia: Documento in Post-print
Dimensione 376.66 kB
Formato Adobe PDF
376.66 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11564/691672
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact