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

DOI10.1137/070693217zbMath1181.05079MaRDI 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 analysis; analysis of algorithms; data structures; minimum spanning trees; pointer machine; flowgraphs; set union; path compression; random-access machine; nearest common ancestors; component tree; finding dominators

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68N20: Theory of compilers and interpreters

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

Related Items

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