Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems

DOI10.1137/070693217zbMath1181.05079OpenAlexW2014665344MaRDI QIDQ3395044

Haim Kaplan, Anne Rogers, Loukas Georgiadis, Jeffery Westbrook, Robert Endre Tarjan, Adam L. Buchsbaum

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

zbMATH Keywords

interval analysisanalysis of algorithmsdata structuresminimum spanning treespointer machineflowgraphsset unionpath compressionrandom-access machinenearest common ancestorscomponent treefinding dominators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Theory of compilers and interpreters (68N20) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (23)

On computing the 2-vertex-connected components of directed graphs ⋮ Strong articulation points and strong bridges in large scale graphs ⋮ Succinct indices for path minimum, with applications ⋮ 2-Vertex Connectivity in Directed Graphs ⋮ Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ 2-vertex connectivity in directed graphs ⋮ Computing Critical Nodes in Directed Graphs ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Finding dominators via disjoint set union ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Efficient computation of arbitrary control dependencies ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Finding strong bridges and strong articulation points in linear time ⋮ A simplified algorithm computing all \(s-t\) bridges and articulation points ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Computing the 2-blocks of directed graphs ⋮ Computing 2-twinless blocks ⋮ Safety in \(s\)-\(t\) paths, trails and walks

This page was built for publication: Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems