Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/4236
Título: | Dominating induced matchings |
Autor: | Cardoso, Domingos M. Lozin, V. V. |
Palavras-chave: | Dominating induced matching Efficient edge dominating set Induced matchings NP Complete Polynomial-time algorithm Regular graphs Graph theory |
Data: | 2009 |
Editora: | Springer Verlag |
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. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/4236 |
ISSN: | 0302-9743 |
Versão do Editor: | http://www.springerlink.com/content/0wl40084n5854077 |
Aparece nas coleções: | DMat - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
54200077.pdf | Versão Electrónica | 149.41 kB | Adobe PDF |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.