ICS Theory Group

Spring 2017: Theory Seminar
Bren Hall, Room 1423, 1:00pm


April 21, 2017:

On the Fixed Parameter Tractability of Leaf Power Graphs

Elham Havvaei

Abstract: A k-leaf power of a tree T, is a graph G whose vertices are the leaves of T and two vertices in G are adjacent if the associated vertices in T have a distance of at most k. A graph is called a leaf power if it is a k-leaf power of a tree for a constant k. Recognition of k-leaf powers, for k at least 5, is still an open problem. In this talk, we show that the recognition of sparse k-leaf powers with bounded degeneracy can be done in linear time.

Joint work with David Eppstein