### Abstract

We present a linear-time algorithm that given a flowgraph G = (V, A, r) and a tree T, checks whether T is the dominator tree of G. Also we prove that there exist two spanning trees of G, T _{1} and T _{2}, such that for any vertex v the paths from r to v in T _{1} and T _{2} intersect only at the vertices that dominate v. The proof is constructive and our algorithm can build the two spanning trees in linear time. Simpler versions of our two algorithms run in O(mα(m, n))-time, where n is the number of vertices and m is the number of arcs in G. The existence of such two spanning trees implies that we can order the calculations of the iterative algorithm for finding dominators, proposed by Allen and Cocke [2], so that it builds the dominator tree in a single iteration.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 433-442 |

Number of pages | 10 |

State | Published - Jul 1 2005 |

Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |

### Other

Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | Vancouver, BC |

Period | 1/23/05 → 1/25/05 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Dominator tree verification and vertex-disjoint paths'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 433-442)