Dominating induced matchings
| Data(s) |
31/10/2011
2009
|
|---|---|
| Resumo |
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. CEOC FCT FEDER/POCI/2010 DIMAP |
| Identificador |
0302-9743 |
| Idioma(s) |
eng |
| Publicador |
Springer Verlag |
| Relação |
http://www.scopus.com/inward/record.url?eid=2-s2.0-70249130892&partnerID=40&md5=3bd3b9d4aa3327d73391ca0a3c92aaea http://www.springerlink.com/content/0wl40084n5854077 |
| Direitos |
restrictedAccess restrictedAccess |
| Palavras-Chave | #Dominating induced matching #Efficient edge dominating set #Induced matchings #NP Complete #Polynomial-time algorithm #Regular graphs #Graph theory |
| Tipo |
article |
