Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
DOI10.1137/070693217zbMATH Open1181.05079OpenAlexW2014665344MaRDI QIDQ3395044FDOQ3395044
Authors: Loukas Georgiadis, Haim Kaplan, Anne Rogers, Adam L. Buchsbaum, Robert E. Tarjan, Jeffery R. Westbrook 
Publication date: 20 August 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070693217
Recommendations
analysis of algorithmsdata structuresinterval analysispointer machineminimum spanning treesflowgraphsset unionpath compressionrandom-access machinenearest common ancestorscomponent treefinding dominators
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Nonnumerical algorithms (68W05) Theory of compilers and interpreters (68N20)
Cited In (31)
- Finding dominators via disjoint set union
- Algorithms – ESA 2004
- On computing the 2-vertex-connected components of directed graphs
- Finding strong bridges and strong articulation points in linear time
- On the graph traversal method for evaluating linear binary-chain programs
- Succinct indices for path minimum, with applications
- Computing the 2-blocks of directed graphs
- Strong articulation points and strong bridges in large scale graphs
- Safety in \(s\)-\(t\) paths, trails and walks
- Efficient computation of arbitrary control dependencies
- Title not available (Why is that?)
- 2-vertex connectivity in directed graphs
- Disjoint set forest digraph representation for an efficient dominator tree construction
- 2-vertex connectivity in directed graphs
- Finding 2-edge and 2-vertex strongly connected components in quadratic time
- Dominator tree certification and divergent spanning trees
- Dominators, directed bipolar orders, and independent spanning trees
- Finding dominators revisited (extended abstract)
- Computing 2-twinless blocks
- Fault-tolerant subgraph for single-source reachability: general and optimal
- Sparse certificates for 2-connectivity in directed graphs
- Strong connectivity in directed graphs under failures, with applications
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Dominator tree verification and vertex-disjoint paths
- On 2-strong connectivity orientations of mixed graphs and related problems
- A simplified algorithm computing all \(s\)-\(t\) bridges and articulation points
- Computing Resolution-Path Dependencies in Linear Time ,
- Computing Critical Nodes in Directed Graphs
- Dynamic Dominators and Low-High Orders in DAGs
- Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
This page was built for publication: Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3395044)
