Finding dominators via disjoint set union

Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)2-20
Number of pages19
JournalJournal of Discrete Algorithms
Volume23
DOIs
StatePublished - Nov 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Depth-first search
  • Directed graph
  • Disjoint set union
  • Dominators
  • Flow graph
  • Global code optimization
  • Program certification

Fingerprint Dive into the research topics of 'Finding dominators via disjoint set union'. Together they form a unique fingerprint.

Cite this