Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/4236
Title: | Dominating induced matchings |
Author: | Cardoso, Domingos M. Lozin, V. V. |
Keywords: | Dominating induced matching Efficient edge dominating set Induced matchings NP Complete Polynomial-time algorithm Regular graphs Graph theory |
Issue Date: | 2009 |
Publisher: | Springer Verlag |
Abstract: | We study the problem of determining whether or not a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general as well as in some restricted domains, such as bipartite graphs or regular graphs. In this paper, we identify a graph parameter to which the complexity of the problem is sensible and produce results of both negative (intractable) and positive (solvable in polynomial time) type. © 2009 Springer Berlin Heidelberg. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/4236 |
ISSN: | 0302-9743 |
Publisher Version: | http://www.springerlink.com/content/0wl40084n5854077 |
Appears in Collections: | DMat - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
54200077.pdf | Versão Electrónica | 149.41 kB | Adobe PDF | ![]() |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.