Finding Dominators in Directed Graphs

作     者：Robert Tarjan 

出 版 物：《SIAM Journal on Computing》 

年 卷 期：1974年第3卷第1期

页      面：62-89页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：algorithm binary tree complexity connectivity depth-first search directed graph dominator equivalence algorithm graph immediate dominator priority queue search set union stack topological sorting tree 

摘      要：This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and manipulating priority queues to achieve a time bound of O(VlogV+E) role=presentationO(VlogVspan class=mo id=MathJax-Span-9 style=font-family: MathJ