Dominator tree verification and vertex-disjoint paths

Loukas Georgiadis, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages433-442
Number of pages10
StatePublished - Jul 1 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/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

    Georgiadis, L., & Tarjan, R. E. (2005). Dominator tree verification and vertex-disjoint paths. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 433-442)