Finding Dominators in Directed Graphs

DOI10.1137/0203006MaRDI QIDQ4050114zbMATH OpenOpenAlexFDO

Authors Robert E. Tarjan

Publication date 1974

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/87503d0db5151491c26134b03ca6158040f5f91e

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Cited in

(40)

• Pseudo-recursive procedures
• On efficient parallel strong orientation
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Notes on oriented depth-first search and longest paths
• Depth-first K-trees and critical path analysis
• Pathlistings applied to data flow analysis
• st-ordering the vertices of biconnected graphs
• Efficient parallel algorithms for path problems in directed graphs
• Parallel search algorithms for graphs and trees
• A new algorithm for finding weak components
• Edge-disjoint spanning trees and depth-first search
• Testing flow graph reducibility
• Correctness of parallel programs: The Church-Rosser approach
• A linear-time algorithm for finding all feedback vertices
• A uniform approach to semi-dynamic problems on digraphs
• Self-stabilizing depth-first token circulation on networks
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Minimization algorithms for sequential transducers
• 2-vertex connectivity in directed graphs
• An \(O(| V|^*| E|)\) algorithm for finding immediate multiple-vertex dominators
• Concurrent disjoint set union
• Dijkstra graphs
• Propositional SAT solving
• 2-vertex connectivity in directed graphs
• A simple and optimal ancestry labeling scheme for trees
• Parallel algorithms for connectivity problems in graph theory
• Computing Critical Nodes in Directed Graphs
• Generalized dominators for structured programs
• Dynamic Dominators and Low-High Orders in DAGs
• Depth First Search in the Semi-streaming Model
• Indexing graph search trees and applications
• Strong connectivity in directed graphs under failures, with applications
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• A quadratic algorithm for finding next-to-shortest paths in graphs
• Counting edges in a dag
• Generalized dominators
• Computing the 4-edge-connected components of a graph: an experimental study
• Faster dynamic 2-edge connectivity in directed graphs
• A simple version of Karzanov's blocking flow algorithm
• A parallel search algorithm for directed acyclic graphs

This page was built for publication: Finding Dominators in Directed Graphs

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