Dominator tree verification and vertex-disjoint paths

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, T1 and T2, such that for any vertex <u>v</u> the paths from r to <u>v</u> in T1 and T2 intersect only at the vertices that dominate <u>v</u>. 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.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: F. E. Allen and J. Cocke. Graph theoretic constructs for program control flow analysis. Technical Report IBM Res. Rep. RC 3923, IBM T.J. Watson Research Center, 1972.
• 3: Stephen Alstrup , Dov Harel , Peter W. Lauridsen , Mikkel Thorup, Dominators in Linear Time, SIAM Journal on Computing, v.28 n.6, p.2117-2132, Dec. 1999 [doi>10.1137/S0097539797317263]
• 4: M. Enamul Amyeen , W. Kent Fuchs , Irith Pomeranz , Vamsi Boppana, Fault Equivalence Identification Using Redundancy Information and Static and Dynamic Extraction, Proceedings of the 19th IEEE VLSI Test Symposium, p.124, March 29-April 03, 2001
• 5: A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook. Linear-time pointer-machine algorithms for least common ancestors, mst verification, and dominators. In preparation.
• 6: Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.279-288, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276764]
• 7: Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998 [doi>10.1145/295656.295663]
• 8: K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Available online at http://www.cs.rice.edu/~keith/EMBED/dom.pdf.
• 9: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 10: Brandon Dixon , Monika Rauch , Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing, v.21 n.6, p.1184-1192, Dec. 1992 [doi>10.1137/0221070]
• 11: H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2):209--21, 1985.
• 12: Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 13: L. Georgiadis, R. F. Werneck, R. E. Tarjan, S. Triantafyllis, and D. I. August. Finding dominators in practice. In 12th Annual European Symposium on Algorithms, pages 677--688, 2004.
• 14: David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
• 15: V. King. A simpler minimum spanning tree verification algorithm. Algorithmica, 18:263--70, 1997.
• 16: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 17: G. Ramalingam , Thomas Reps, An incremental algorithm for maintaining the dominator tree of a reducible flowgraph, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.287-296, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177905]
• 18: M. Sharir. Structural analysis: A new approach to flow analysis in optimizing compilers. volume 5, pages 141--153, 1980.
• 19: Philip H. Sweany , Steven J. Beaty, Dominator-path scheduling: a global scheduling method, Proceedings of the 25th annual international symposium on Microarchitecture, p.260-263, December 01-04, 1992, Portland, Oregon, United States
• 20: R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146--59, 1972.
• 21: Robert Tarjan, Testing flow graph reducibility, Proceedings of the fifth annual ACM symposium on Theory of computing, p.96-107, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804040]
• 22: R. E. Tarjan. Edge-disjoint spanning trees and depth-first search. Acta Informatica, 6(2):171--85, 1976.
• 23: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
• 24: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• 25: R. W. Whitty. Vertex-disjoint paths and edge-disjoint branchings in directed graphs. Journal of Graph Theory, 11:349--358, 1987.
• 26: A. Wirth. Manuscript, 2003.