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

Ejemplares similares

Ejemplares similares