The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

PLG

Seminar

On (k.l)-leaf powers

Wagner, P (Rostock)
Tuesday 18 December 2007, 15:30-15:50

Seminar Room 1, Newton Institute

Abstract

We say that, for k>1 and l>k, a tree T is a (k,l)-leaf root of a graph G=(V,E), if V is the set of leaves of T, for all edges xy in E, the distance d(x,y) between x and y in T (i.e., the number of edges of the unique path between the leaves x and y in T) is at most k and, for all non-edges xy outside E, d(x,y) is at least l. A graph G is a (k,l)-leaf power, if it has a (k,l)-leaf root.

This new notion generalises the concept of k-leaf power, which was introduced and studied by Nishimura, Ragde and Thilikos in 2002, motivated by the search for underlying phylogenetic trees: "...a fundamental problem in computational biology is the reconstruction of the phylogeny, or evolutionary history, of a set of species or genes, typically represented as a phylogenetic tree..." The species occur as leaves of the phylogenetic tree.

Recently, a lot of work has been done on k-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. For k=3 and k=4, structural characterisations and linear time recognition algorithms of k-leaf powers are known, and, recently, a polynomial time recognition of 5-leaf powers was given. For larger k, the recognition problem is open. We give structural characterisations of (k,l)-leaf powers, for some k and l, which also imply efficient recognition of these classes, and in this way we also improve and extend a recent paper from 2006 by Kennedy, Lin and Yan on strictly chordal graphs and leaf powers.

Presentation

[ppt ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧