Please use this identifier to cite or link to this item:
|Title:||Dominating induced matchings|
|Author:||Cardoso, Domingos M.|
Lozin, V. V.
|Keywords:||Dominating induced matching|
Efficient edge dominating set
|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.|
|Appears in Collections:||DMat - Artigos|
Files in This Item:
|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.