On the Complexity of {k}-domination for Chordal Graphs
In this work we obtain a new graph class where {k}-DOM is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. By relating this problem with k-DOM, we prove that {k}-DOM is polynomial time solvable for strongly chordal graphs. B...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Inglés |
| Publicado: |
2013
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/94545 |
| Aporte de: |
| Sumario: | In this work we obtain a new graph class where {k}-DOM is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. By relating this problem with k-DOM, we prove that {k}-DOM is polynomial time solvable for strongly chordal graphs. Besides, by expressing the property involved in k-DOM in Counting Monadic Second- order Logic, we obtain that both problems are linear time solvable for bounded tree-width graphs. In this way we enlarge the family of graphs for which k-DOM is polynomial time solvable. |
|---|