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
id I19-R120-10915-94545
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Chordal graphs
k-DOM
spellingShingle Ciencias Informáticas
Chordal graphs
k-DOM
Argiroffo, G.
Leoni, V.
Torres, P.
On the Complexity of {k}-domination for Chordal Graphs
topic_facet Ciencias Informáticas
Chordal graphs
k-DOM
description 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.
format Objeto de conferencia
Resumen
author Argiroffo, G.
Leoni, V.
Torres, P.
author_facet Argiroffo, G.
Leoni, V.
Torres, P.
author_sort Argiroffo, G.
title On the Complexity of {k}-domination for Chordal Graphs
title_short On the Complexity of {k}-domination for Chordal Graphs
title_full On the Complexity of {k}-domination for Chordal Graphs
title_fullStr On the Complexity of {k}-domination for Chordal Graphs
title_full_unstemmed On the Complexity of {k}-domination for Chordal Graphs
title_sort on the complexity of {k}-domination for chordal graphs
publishDate 2013
url http://sedici.unlp.edu.ar/handle/10915/94545
work_keys_str_mv AT argiroffog onthecomplexityofkdominationforchordalgraphs
AT leoniv onthecomplexityofkdominationforchordalgraphs
AT torresp onthecomplexityofkdominationforchordalgraphs
bdutipo_str Repositorios
_version_ 1764820491542986753

Ejemplares similares