A new, simpler linear-time dominators algorithm
A new, simpler linear-time dominators algorithm
复制标题
DOI：
10.1145/295656.295663
复制
发表时间：
1998-11-01
影响因子：
1.3
通讯作者：
Westbrook, JR
中科院分区：
文献类型：
--
作者：
Buchsbaum, AL;Kaplan, H;Westbrook, JR
我们提出了一种新的线性时间算法来寻找流图中所有顶点的直接支配。我们的算法比以前的线性时间算法更简单：我们没有使用复杂的数据结构，而是将微树和记忆法的使用与对受限类路径压缩的新观察相结合。我们已经实现了我们的算法，我们报告了实验结果，表明常量因子很低。与Lengauer和Tarjan的标准的略微超线性的算法相比，我们的算法在合理大小的真实流图上运行速度慢10%-20%，在非常大的流图上仅慢几个百分点。
We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data structures, we combine the use of microtrees and memoization with new observations on a restricted class of path compressions. We have implemented our algorithm, and we report experimental results that-show that the constant factors are low. Compared to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flowgraphs of reasonable size and only a few percent slower on very large flowgraphs.