Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 On the complexity of the dominating induced matching problem in hereditary classes of graphs
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4233

title: On the complexity of the dominating induced matching problem in hereditary classes of graphs
authors: Cardoso, D.M.
Korpelainen, N.
Lozin, V.V.
keywords: Dominating induced matching
Polynomial-time algorithm
Claw-free graphs
Efficient edge dominating set
Induced matchings
Special graph class
Computational complexity
issue date: 2011
publisher: Elsevier
abstract: The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a "boundary" separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs. © 2010 Elsevier B.V. All rights reserved.
URI: http://hdl.handle.net/10773/4233
ISSN: 0166-218X
publisher version/DOI: http://www.sciencedirect.com/science/article/pii/S0166218X10001174
source: Discrete Applied Mathematics
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
CardosoKorpelainenLozin.pdfElectronic Version290.08 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2