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
Author: 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.
Peer review: yes
URI: http://hdl.handle.net/10773/4233
ISSN: 0166-218X
Publisher Version: http://www.sciencedirect.com/science/article/pii/S0166218X10001174
Appears in Collections:MAT - Artigos

Files in This Item:
File Description SizeFormat 
CardosoKorpelainenLozin.pdfElectronic Version290.08 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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