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" [...]

 

  Payday Loans In Texas. In this section we give only a brief summary recommendation for admission of Canadian Levitra. Full information can be found in the instructions for receiving medications with vardenafil.