Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 Dominating induced matchings
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4236

title: Dominating induced matchings
authors: 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.
URI: http://hdl.handle.net/10773/4236
ISSN: 0302-9743
publisher version/DOI: http://www.springerlink.com/content/0wl40084n5854077
source: Lecture Notes in Computer Science
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
54200077.pdfVersão Electrónica149.41 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

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


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2