Computer Science

Speaker: Juraj Stacho
Department of Computer Science
University of Toronto

Title: Polynomial-time algorithm for the leafage of chordal graphs

Abstract: Every chordal graph G can be represented as the intersection graph of a collection of subtrees of a host tree, the so-called tree model of G. The leafage l(G) of a connected chordal graph G is the minimum number of leaves of the host tree of a tree model of G.  This concept was first defined by I.-J. Lin, T.A. McKee, and D.B. West. In this talk, we present the first polynomial time algorithm for computing the leafage of chordal graphs. The algorithm is based on a notion of augmenting paths similar to that of matching theory. In fact, it runs in time O(n^3) and it not only computes l(G) but also constructs a tree model of G with minimum number of leaves in the host tree. In addition, we discuss a connection to the matriod intersection algorithm and to the problem of finding a maximum spanning tree with minimum
number of leaves.