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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Argiroffo, G., Leoni, V., Torres, P.
Formato: Objeto de conferencia Resumen
Lenguaje:Inglés
Publicado: 2013
Materias:
Ciencias Informáticas
Chordal graphs
k-DOM
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/94545
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata

Ejemplares similares

Ejemplares similares