Finding Dominators in Directed Graphs
From MaRDI portal
Publication:4050114
DOI10.1137/0203006zbMath0296.68030OpenAlexW2049105156MaRDI QIDQ4050114
Publication date: 1974
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/87503d0db5151491c26134b03ca6158040f5f91e
Directed graphs (digraphs), tournaments (05C20) General topics in the theory of software (68N01) Algorithms in computer science (68W99)
Related Items (37)
On efficient parallel strong orientation ⋮ Rectilinear planar layouts and bipolar orientations of planar graphs ⋮ 2-Vertex Connectivity in Directed Graphs ⋮ A Simple and Optimal Ancestry Labeling Scheme for Trees ⋮ Propositional SAT Solving ⋮ 2-vertex connectivity in directed graphs ⋮ Computing Critical Nodes in Directed Graphs ⋮ Notes on oriented depth-first search and longest paths ⋮ Dijkstra graphs ⋮ Depth-first K-trees and critical path analysis ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Pathlistings applied to data flow analysis ⋮ A quadratic algorithm for finding next-to-shortest paths in graphs ⋮ st-ordering the vertices of biconnected graphs ⋮ Parallel algorithms for connectivity problems in graph theory ⋮ Efficient parallel algorithms for path problems in directed graphs ⋮ Generalized dominators ⋮ Parallel search algorithms for graphs and trees ⋮ A new algorithm for finding weak components ⋮ Generalized dominators for structured programs ⋮ Edge-disjoint spanning trees and depth-first search ⋮ Testing flow graph reducibility ⋮ Unnamed Item ⋮ Correctness of parallel programs: The Church-Rosser approach ⋮ A linear-time algorithm for finding all feedback vertices ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Depth First Search in the Semi-streaming Model ⋮ A uniform approach to semi-dynamic problems on digraphs ⋮ Concurrent disjoint set union ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Minimization algorithms for sequential transducers ⋮ An \(O(| V|^*| E|)\) algorithm for finding immediate multiple-vertex dominators ⋮ A simple version of Karzanov's blocking flow algorithm ⋮ A parallel search algorithm for directed acyclic graphs ⋮ Pseudo-recursive procedures ⋮ Self-stabilizing depth-first token circulation on networks ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
This page was built for publication: Finding Dominators in Directed Graphs
