Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/4236| 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 |
| URI: | http://hdl.handle.net/10773/4236 |
| ISSN: | 0302-9743 |
| Publisher Version: | http://www.springerlink.com/content/0wl40084n5854077 |
| Appears in Collections: | DMat - Artigos |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 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.