Lecture
Linear-time algorithms for independent trees
and directed s-t numberings of directed graphs
Speaker: |
Loukas Georgiadis |
Date: |
Tuesday, 17 July 2007 |
Time: |
12:00-13:30 |
Location: |
Seminar Room I, Building C, FORTH. Heraklion, Crete |
Host: |
Ioannis Tollis |
Abstract: |
Consider a directed graph
G=(V,A) with the property that every vertex in V is reachable
from a distinguished root vertex r. We say that a vertex w dominates
a vertex v if every path from r to v includes w; r and v are the
trivial dominators of v. A theorem by Whitty states that if every
vertex in G has only trivial dominators then G has two spanning
trees such that, for any vertex v, their r-v paths are vertex-disjoint.
Trees that satisfy this property are called independent. Whitty
only claimed a polynomial running time for the complicated algorithm
implied by his proof. A simpler construction was given by Cheriyan
and Reif, based on the notion of directed s-t numberings. They
showed how to construct a numbering f: V -> {1,...,n}, such that
each vertex v in V-r has predecessors u and w that satisfy f(u)
< f(v) < f(w). However, they did not determine the time complexity
for this construction. Later Huck gave another algorithm for two
independent spanning trees running in O(|V||A|) time. In this talk we generalize the notions of independent spanning trees and directed s-t numberings for graphs that may have non-trivial dominators, and describe corresponding simple linear-time algorithms. Specifically, we show that G has two spanning trees such that, for any vertex v, their r-v paths intersect only at the dominators of v. Then we describe how to obtain from these spanning trees a directed s-t numbering of G. (Joint work with Bob Tarjan) |
Bio: |
I received the diploma in Computer Engineering and Informatics from the
University of Patras in 1999, where I remained as a graduate student for
the year 1999-2000. After that I was a graduate student at the
department of Computer Science of Princeton University where I obtained
the MA in 2002 and the PhD in 2005. During the year 2005-2006 I have
been a postdoctoral researcher of the department of Informatics at the
University of Aarhus in Denmark. Currently I am a member of the Applied
Algorithms Group of Hewlett-Packard Laboratories in Palo Alto,
California. |