On the complexity of the labeled domination problem in graphs
| Autor: | Argiroffo, Gabriela Rut, Leoni, Valeria Alejandra, Torres, Pablo Daniel |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | CONICET Digital (CONICET) Consejo Nacional de Investigaciones Científicas y Técnicas instacron:CONICET |
| Popis: | 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. Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina Fil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|