| dc.creator | Argiroffo, Gabriela Rut | |
| dc.creator | Leoni, Valeria Alejandra | |
| dc.creator | Torres, Pablo Daniel | |
| dc.date.accessioned | 2018-07-26T19:20:53Z | |
| dc.date.available | 2018-07-26T19:20:53Z | |
| dc.date.created | 2018-07-26T19:20:53Z | |
| dc.date.issued | 2017-01 | |
| dc.identifier | Argiroffo, Gabriela Rut; Leoni, Valeria Alejandra; Torres, Pablo Daniel; On the complexity of the labeled domination problem in graphs; Blackwell Publishers; International Transactions in Operational Research; 24; 1-2; 1-2017; 355-367 | |
| dc.identifier | 0969-6016 | |
| dc.identifier | http://hdl.handle.net/11336/53215 | |
| dc.identifier | CONICET Digital | |
| dc.identifier | CONICET | |
| dc.description.abstract | In 2008, a unified approach (labeled domination) to several domination problems (k-tuple domination, {k} -domination, and M-domination, among others) was introduced. The labeled domination problem is to find an L-dominating function of minimum weight in a graph. It is an NP-complete problem even when restricted to split graphs and bipartite graphs. On the other hand, it is known to be polynomial-time solvable for the class of strongly chordal graphs. In this paper, we state explicit formulas that relate the domination numbers considered. These relationships allow us to enlarge the family of graphs where the labeled domination problem is polynomial-time solvable to the class of graphs having cliquewidth bounded by a constant. | |
| dc.language | eng | |
| dc.publisher | Blackwell Publishers | |
| dc.relation | info:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1111/itor.12286 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12286 | |
| dc.rights | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.subject | Computational Complexity | |
| dc.subject | K-Tuple Dominating Function | |
| dc.subject | Labeled Dominating Function | |
| dc.subject | {K}-Dominating Function | |
| dc.title | On the complexity of the labeled domination problem in graphs | |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
