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: | DMat - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CardosoKorpelainenLozin.pdf | Electronic Version | 290.08 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.