Finding dominators via disjoint set union

DOI10.1016/j.jda.2013.10.003zbMath1294.05148arXiv1310.2118OpenAlexW2001331197MaRDI QIDQ396673

Mohammad Hasan, H. S. Yoon

Publication date: 13 August 2014

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

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

zbMATH Keywords

dominatorsdirected graphdepth-first searchdisjoint set unionflow graphglobal code optimizationprogram certification

Mathematics Subject Classification ID

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

Related Items (5)

2-vertex connectivity in directed graphs ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Concurrent disjoint set union

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Testing flow graph reducibility
• Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions
• Dominators, Directed Bipolar Orders, and Independent Spanning Trees
• Disjoint Set Forest Digraph Representation for an Efficient Dominator Tree Construction
• Applications of Path Compression on Balanced Trees
• Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph
• 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
• Worst-case Analysis of Set Union Algorithms
• A fast algorithm for finding dominators in a flowgraph
• Characterizations of Reducible Flow Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• On Finding Lowest Common Ancestors in Trees
• Dominators in Linear Time
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
• Mechanized Verification of Computing Dominators for Formalizing Compilers
• Finding Dominators in Practice
• Depth-First Search and Linear Graph Algorithms

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