Linear-time algorithms for independent trees and directed s-t numberings of directed graphs
Speaker: Loukas Georgiadis
Date: 17 July 2007 Time: 12:00-13:30
Location: Seminar Room I, Building C, FORTH, Heraklion, Crete.
Host: Ioannis Tollis


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)


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.

Conditions of Use | Privacy Policy