Determining possible sets of leaves for spanning trees of dually chordal graphs

It will be proved that the problem of determining whether a set of vertices of a dually chordal graphs is the set of leaves of a tree compatible with it can be solved in polynomial time by establishing a connection with finding clique trees of chordal graphs with minimum number of leaves.

Guardado en:
Detalles Bibliográficos
Autores principales: De Caria, Pablo Jesús, Gutiérrez, Marisa
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2009
Materias:
Matemática
Leaf
Compatible tree
Clique tree
Chordal
Dually chordal
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/93883
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-93883
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Leaf
Compatible tree
Clique tree
Chordal
Dually chordal
spellingShingle Matemática
Leaf
Compatible tree
Clique tree
Chordal
Dually chordal
De Caria, Pablo Jesús
Gutiérrez, Marisa
Determining possible sets of leaves for spanning trees of dually chordal graphs
topic_facet Matemática
Leaf
Compatible tree
Clique tree
Chordal
Dually chordal
description It will be proved that the problem of determining whether a set of vertices of a dually chordal graphs is the set of leaves of a tree compatible with it can be solved in polynomial time by establishing a connection with finding clique trees of chordal graphs with minimum number of leaves.
format Objeto de conferencia
Objeto de conferencia
author De Caria, Pablo Jesús
Gutiérrez, Marisa
author_facet De Caria, Pablo Jesús
Gutiérrez, Marisa
author_sort De Caria, Pablo Jesús
title Determining possible sets of leaves for spanning trees of dually chordal graphs
title_short Determining possible sets of leaves for spanning trees of dually chordal graphs
title_full Determining possible sets of leaves for spanning trees of dually chordal graphs
title_fullStr Determining possible sets of leaves for spanning trees of dually chordal graphs
title_full_unstemmed Determining possible sets of leaves for spanning trees of dually chordal graphs
title_sort determining possible sets of leaves for spanning trees of dually chordal graphs
publishDate 2009
url http://sedici.unlp.edu.ar/handle/10915/93883
work_keys_str_mv AT decariapablojesus determiningpossiblesetsofleavesforspanningtreesofduallychordalgraphs
AT gutierrezmarisa determiningpossiblesetsofleavesforspanningtreesofduallychordalgraphs
bdutipo_str Repositorios
_version_ 1764820491885871104

Ejemplares similares