Can I read A New, Simpler Linear-time Dominators Algorithm on EtoBox?

A New, Simpler Linear-time Dominators Algorithm by Adam L. Buchsbaum; Haim Kaplan; Anne Rogers; Jeffery R. Westbrook is a Computer Science article available to read on EtoBox.

What is A New, Simpler Linear-time Dominators Algorithm about?

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.

Who reads A New, Simpler Linear-time Dominators Algorithm?

Author

Adam L. Buchsbaum; Haim Kaplan; Anne Rogers; Jeffery R. Westbrook

Publisher

ACM

Published

1998

Language

EN

Field

Computer Science (Physical Sciences)