Geodesic
Finding Dominators in Practice
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004) , Tome 10 (2006) no. 1, pp. 69-94.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The computation of dominators in a flowgraph has applications in several areas, including program optimization, circuit testing, and theoretical biology. Lengauer and Tarjan [] proposed two versions of a fast algorithm for finding dominators and compared them experimentally with an iterative bit-vector algorithm. They concluded that both versions of their algorithm were much faster even on graphs of moderate size. Recently Cooper et al. [] have proposed a new, simple, tree-based implementation of an iterative algorithm. Their experiments suggested that it was faster than the simple version of the Lengauer-Tarjan algorithm on graphs representing computer program control flows. Motivated by the work of Cooper et al., we present an experimental study comparing their algorithm (and some variants) with careful implementations of both versions of the Lengauer-Tarjan algorithm and with a new hybrid algorithm. Our results suggest that, although the performance of all the algorithms is similar, the most consistently fast are the simple Lengauer-Tarjan algorithm and the hybrid algorithm, and their advantage increases as the graph gets bigger or more complicated.
DOI : 10.7155/jgaa.00119
Keywords: dominators, flowgraphs, control flow analysis, program optimization, experimental evaluation, path compression, Lengauer-Tarjan, iterative algorithm 
@article{JGAA_2006_10_1_a3,
     author = {Loukas Georgiadis and Robert Tarjan and Renato Werneck},
     title = {Finding {Dominators} in {Practice}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {69--94},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2006},
     doi = {10.7155/jgaa.00119},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00119/}
}
TY  - JOUR
AU  - Loukas Georgiadis
AU  - Robert Tarjan
AU  - Renato Werneck
TI  - Finding Dominators in Practice
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 69
EP  - 94
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00119/
DO  - 10.7155/jgaa.00119
LA  - en
ID  - JGAA_2006_10_1_a3
ER  - 
%0 Journal Article
%A Loukas Georgiadis
%A Robert Tarjan
%A Renato Werneck
%T Finding Dominators in Practice
%J Journal of Graph Algorithms and Applications
%D 2006
%P 69-94
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00119/
%R 10.7155/jgaa.00119
%G en
%F JGAA_2006_10_1_a3
Loukas Georgiadis; Robert Tarjan; Renato Werneck. Finding Dominators in Practice. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004)
					, Tome 10 (2006) no. 1, pp. 69-94. doi : 10.7155/jgaa.00119. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00119/

Cité par Sources :