Skip to main content

Finding dominators via disjoint set union

Author(s): Fraczak, Wojciech; Georgiadis, Loukas; Miller, Andrew; Tarjan, Robert E

To refer to this page use:
Abstract: The problem of finding dominators in a directed graph has many important applications, notably in global optimization of computer code. Although linear and near-linear-time algorithms exist, they use sophisticated data structures. We develop an algorithm for finding dominators that uses only a “static tree” disjoint set data structure in addition to simple lists and maps. The algorithm runs in near-linear or linear time, depending on the implementation of the disjoint set data structure. We give several versions of the algorithm, including one that computes loop nesting information (needed in many kinds of global code optimization) and that can be made self-certifying, so that the correctness of the computed dominators is very easy to verify.
Publication Date: Nov-2013
Citation: Fraczak, Wojciech, Loukas Georgiadis, Andrew Miller, and Robert E. Tarjan. "Finding dominators via disjoint set union." Journal of Discrete Algorithms 23 (2013): 2-20. doi:10.1016/j.jda.2013.10.003
DOI: 10.1016/j.jda.2013.10.003
ISSN: 1570-8667
Pages: 2 - 20
Type of Material: Journal Article
Journal/Proceeding Title: Journal of Discrete Algorithms
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.