**Thursday, 13:15 - 13:40 h, Room: H 3503**

**Álvaro Franco**

A new linear time algorithm to construct dominator trees of reducible flow graphs

**Coauthor: Carlos Eduardo Ferreira**

**Abstract:**

A flow graph *G = (V, E, r)* is a directed graph, where *r* is a vertex in *G* that reaches any vertex *v* in *G*. A vertex *w* dominates vertex *v* if any path from *r* to *v* passes through *w*. A vertex *w* is the immediate dominator of *v* (*\mathrm{id}(v) = w*) if *w* dominates *v* and any dominator of *v* dominates *w*. It is well known that for each vertex *v ≠ r* there is a single vertex *w* that dominates immediately *v*. The graph *T = (V, E*^{\}prime), where *E*^{\}prime = {(\mathrm{id}(v),v):v ∈ V\{r}} is a rooted tree (root in *r*) called dominator tree of *G*. Sophisticated algorithms have been proposed to construct a dominator tree of a flow graph (e.g., Georgiadis and Tarjan, 2004). Even if the flow graph is reducible the algorithms existing are hard to implement (e.g., the linear implementation of Ramalingam and Reps algorithm, 1994). We develop a linear time algorithm to construct a dominator tree of *G* (reducible). It uses simpler data structures to determine whether there are internally vertex-disjoint paths from *r* to *u* and from *r* to *v*, for all pairs of vertices *u, v* in *G*, and to answer lowest common ancestor queries in a depth-first spanning tree of *G*.

Talk 1 of the contributed session Thu.2.H 3503

**"Paths, trees and flows"** [...]

Cluster 23

**"Telecommunications & networks"** [...]