Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> NOV 13: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
NOV 13: Theory CS Seminar
Event date: Friday, November 13, 2009, at 11:10 AM
Location: Galbraith Bldg, Rm. 244
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.