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 following properties:
If (v,w) belongs to A, then w is a proper ancestor of v.
If (v,w) belongs to C, then w is a child of an ancestor of v (allowing v to be an ancestor of itself).
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
w is an ancestor of v in T' only if w is an ancestor of v in T.
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 simultaneously minimized. The running time of the algorithm is O(m α(m,n)), where n is the number of nodes in T, mn 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 Ackermann's function.

other papers about this subject
Last update: August 16, 2004.