Dominators in linear time

被引：76
作者：
Alstrup, S [1 ]
Harel, D
Lauridsen, PW
Thorup, M
机构：
[1] Univ Copenhagen, Dept Comp Sci, Copenhagen, Denmark
[2] Microsoft Israel Ltd, R&D Ctr, IL-31905 Haifa, Israel
来源：
SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 06期
关键词：
control flow analysis; dominators; algorithms;
D O I：
10.1137/S0097539797317263
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A linear-time algorithm is presented for finding dominators in control flow graphs.
引用
收藏
页码：2117 / 2132
页数：16
相关论文
共 24 条
[1]  
AHO A, 1973, 5 ANN ACM S THEOR CO, P115
[2]  
Aho A.V., 1979, Principles of Compiler Design
[3]  
[Anonymous], THEORY PARSING TRANS
[4]  
BILARDI G, 1996, ACM SIGPLAN C PROGR, P291
[5]  
BUCHSBAUM A, 1998, ANN ACM S THEOR COMP, V30
[6]   EFFICIENTLY COMPUTING STATIC SINGLE ASSIGNMENT FORM AND THE CONTROL DEPENDENCE GRAPH [J].
CYTRON, R ;
FERRANTE, J ;
ROSEN, BK ;
WEGMAN, MN ;
ZADECK, FK .
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1991, 13 (04) :451-490
[7]   Optimal parallel verification of minimum spanning trees in logarithmic time [J].
Dixon, B ;
Tarjan, RE .
ALGORITHMICA, 1997, 17 (01) :11-18
[8]   RELAXED HEAPS - AN ALTERNATIVE TO FIBONACCI HEAPS WITH APPLICATIONS TO PARALLEL COMPUTATION [J].
DRISCOLL, JR ;
GABOW, HN ;
SHRAIRMAN, R ;
TARJAN, RE .
COMMUNICATIONS OF THE ACM, 1988, 31 (11) :1343-1354
[9]   TRANS-DICHOTOMOUS ALGORITHMS FOR MINIMUM SPANNING-TREES AND SHORTEST PATHS [J].
FREDMAN, ML ;
WILLARD, DE .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (03) :533-551
[10]   A LINEAR-TIME ALGORITHM FOR A SPECIAL CASE OF DISJOINT SET UNION [J].
GABOW, HN ;
TARJAN, RE .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (02) :209-221
123