Contents

Ars Combinatoria

  • Research article

Determining Possible Sets of Leaves for Spanning Trees of Dually Chordal Graphs

Pablo De Caria1, Marisa Gutierrez2
1CONICET, Departamento de Matematica, Universidad Nacional de La Plata, C.C. 172, (1900), La Plata, Argentina”
2CONICET, Departamento de Matematica, Universidad Nacional de La Plata, C.C. 172, (1900), La Plata, Argentina
  • Published: 31/07/2015

Abstract

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.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Pablo De Caria, Marisa Gutierrez. Determining Possible Sets of Leaves for Spanning Trees of Dually Chordal Graphs[J], Ars Combinatoria, Volume 122. 13-20. .