Implementation of Effective Dominator Trees Using Eager Reduction Algorithm and Delay Reduction Algorithm

Dae-Sik Lee

Implementation of Effective Dominator Trees Using Eager Reduction Algorithm and Delay Reduction Algorithm

Dae-Sik Lee, Journal of Internet Computing and Services, Vol. 6, No. 6, pp. 117-126, Dec. 2005
Full Text:

Keywords: Flow Garph, sequency reducible algorithm, delay reducible algorithm, Dominator Tree

Abstract

The dominator tree presents the dominance frontier from directed graph to the tree. we present the effective algorithm for constructing the dominator tree from arbitrary directed graph. The reducible flow graph was reduced to dominator tree after dominator calculation. And the irreducible flow graph was constructed to dominator-join graph using join-edge information of information table. For reducing the dominator tree from dominator-join graph, we implement the effective sequency reducible algorithm and delay reducible algorithm. As a result of implementation, we can see that the delay reducible algorithm takes less execution time than the sequency reducible algorithm. Therefore, we can reduce the flow graph to dominator tree effectively.

Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from November 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.

Cite this article

[APA Style]

Lee, D. (2005). Implementation of Effective Dominator Trees Using Eager Reduction Algorithm and Delay Reduction Algorithm. Journal of Internet Computing and Services, 6(6), 117-126.

[IEEE Style]

D. Lee, "Implementation of Effective Dominator Trees Using Eager Reduction Algorithm and Delay Reduction Algorithm," Journal of Internet Computing and Services, vol. 6, no. 6, pp. 117-126, 2005.

[ACM Style]

Dae-Sik Lee. 2005. Implementation of Effective Dominator Trees Using Eager Reduction Algorithm and Delay Reduction Algorithm. Journal of Internet Computing and Services, 6, 6, (2005), 117-126.