Journal of Graph Algorithms and Applications Finding Dominators in Practice
Journal of Graph Algorithms and Applications Finding Dominators in Practice
复制标题
图算法与应用杂志在实践中寻找主导者
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Renato F. Werneck
中科院分区：
文献类型：
--
作者：
L. Georgiadis;R. Tarjan;Renato F. Werneck
流程图中主控器的计算在程序优化、电路测试和理论生物学等领域都有应用。Lengauer和Tarjan[30]提出了两个版本的寻找支配者的快速算法，并将它们与迭代位向量算法进行了实验比较。他们的结论是，即使在中等大小的图表上，他们的两个版本的算法也要快得多。最近，库珀等人。[11]提出了一种新的、简单的、基于树的迭代算法实现。他们的实验表明，在表示计算机程序控制流的图形上，该算法比简单版本的Lengauer-Tarjan算法更快。受Cooper等人工作的启发，我们提供了一项实验研究，将他们的算法(和一些变体)与Lengauer-Tarjan算法的两个版本的仔细实现以及一种新的混合算法进行了比较。我们的结果表明，虽然所有算法的性能相似，但最一致的快速算法是简单的Lengauer-Tarjan算法和混合算法，并且它们的优势随着图的更大或更复杂而增加。
The computation of dominators in a flowgraph has applications in several areas, including program optimization, circuit testing, and theoretical biology. Lengauer and Tarjan [30] 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. [11] 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.