Paul Hilfinger, Eugene L. Lawler, and Günter Rote:
Flattening a rooted tree
In: “Applied Geometry and Discrete Mathematics.” The Victor Klee
Festschrift. Editors: Peter Gritzmann and Bernd Sturmfels. DIMACS series in
discrete mathematics and theoretical computer science, American Mathematical
Society and Association for Computing Machinery, 1991; pp. 335-340,
(Zbl 733.68061, MR #92i:68122).
The following is a graph-theoretic formulation of a problem arising in the
compilation of block-structured programming languages. Let T=(V,E) be
a rooted tree and let A and C be sets of additional arcs with the
It is desired to find a rooted tree T'=(V,E') in which the depth of each
node is as small as possible, subject to the conditions (1), (2), and
- If (v,w) belongs to A, then w is a proper ancestor
- If (v,w) belongs to C, then w is a child of an
ancestor of v (allowing v to be an ancestor of itself).
A simple, almost linear-time, algorithm for constructing an optimal
tree T' is described. The constructed tree T' has the property that
node w is an ancestor of node v in T' only if this is true in every tree
satisfying conditions (1)–(3). Hence the depth ever each node is
The running time of the algorithm is O(m α(m,n)), where n is
the number of nodes in T, m≥n is the total number of arcs
in C and T, and α(m,n) is an
extremely slowly growing function related to the functional inverse of
Last update: August 16, 2004.
- w is an ancestor of v in T' only if w is an ancestor
of v in T.