Finding dominators via disjoint set union

DOI10.1016/J.JDA.2013.10.003zbMATH Open1294.05148arXiv1310.2118OpenAlexW2001331197MaRDI QIDQ396673FDOQ396673

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

Publication date: 13 August 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1310.2118

Recommendations

• Corrections to ``Finding dominators via disjoint set union
• Remarks about disjoint dominating sets
• Disjoint dominating and total dominating sets in graphs
• scientific article; zbMATH DE number 5531984
• Finding dominators revisited (extended abstract)
• scientific article; zbMATH DE number 140152
• Algorithms – ESA 2004
• Finding Dominators in Practice
• scientific article; zbMATH DE number 861343
• Disjoint dominating sets with a perfect matching

zbMATH Keywords

depth-first searchdirected graphdominatorsdisjoint set unionflow graphglobal code optimizationprogram certification

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Title not available (Why is that?)
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
• Title not available (Why is that?)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Dominators in Linear Time
• Finding strong bridges and strong articulation points in linear time
• A linear-time algorithm for a special case of disjoint set union
• Edge-disjoint spanning trees and depth-first search
• Dominators, directed bipolar orders, and independent spanning trees
• Dominator tree verification and vertex-disjoint paths
• Applications of Path Compression on Balanced Trees
• A fast algorithm for finding dominators in a flowgraph
• On Finding Lowest Common Ancestors in Trees
• Finding Dominators in Practice
• Finding dominators revisited (extended abstract)
• Worst-case Analysis of Set Union Algorithms
• Testing flow graph reducibility
• Characterizations of Reducible Flow Graphs
• Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions
• Disjoint set forest digraph representation for an efficient dominator tree construction
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
• Mechanized verification of computing dominators for formalizing compilers

Cited In (17)

• Algorithms – ESA 2004
• Finding Dominators in Practice
• Computing dominators in parallel
• Title not available (Why is that?)
• 2-vertex connectivity in directed graphs
• Disjoint set forest digraph representation for an efficient dominator tree construction
• Dominator tree certification and divergent spanning trees
• Dominators, directed bipolar orders, and independent spanning trees
• Finding dominators revisited (extended abstract)
• Strong connectivity in directed graphs under failures, with applications
• Dominator tree verification and vertex-disjoint paths
• Concurrent disjoint set union
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• On 2-strong connectivity orientations of mixed graphs and related problems
• Dynamic Dominators and Low-High Orders in DAGs
• An experimental study of dynamic dominators
• Nested set union

This page was built for publication: Finding dominators via disjoint set union

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396673)