Please use this identifier to cite or link to this item
|title: ||Dominating induced matchings|
|authors: ||Cardoso, Domingos M.|
Lozin, V. V.
|keywords: ||Dominating induced matching|
Efficient edge dominating set
|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.|
|publisher version/DOI: ||http://www.springerlink.com/content/0wl40084n5854077|
|source: ||Lecture Notes in Computer Science|
|appears in collections||MAT - Artigos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.