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
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
ISSN: 0302-9743
Publisher Version:
Appears in Collections:DMat - Artigos

Files in This Item:
File Description SizeFormat 
54200077.pdfVersão Electrónica149.41 kBAdobe PDFrestrictedAccess

Formato BibTex MendeleyEndnote Degois 

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