Dominator tree verification and vertex-disjoint paths

Loukas Georgiadis, Robert E. Tarjan

Research output: Contribution to conferencePaperpeer-review

19 Scopus citations


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)
Number of pages10
StatePublished - 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005


OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


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

Cite this