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)

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)