Dominators in Linear Time

DOI10.1137/S0097539797317263zbMath0939.68158WikidataQ109512904 ScholiaQ109512904MaRDI QIDQ4268860

Dov Harel, Mikkel Thorup, Stephen Alstrup, P. W. Lauridsen

Publication date: 28 October 1999

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

zbMATH Keywords

algorithmsdominatorscontrol flow analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Theory of compilers and interpreters (68N20)

Related Items (21)

On computing the 2-vertex-connected components of directed graphs ⋮ Strong articulation points and strong bridges in large scale graphs ⋮ 2-Vertex Connectivity in Directed Graphs ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ 2-vertex connectivity in directed graphs ⋮ Computing Critical Nodes in Directed Graphs ⋮ Average case analysis of DJ graphs ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Linear time algorithms for two disjoint paths problems on directed acyclic graphs ⋮ Finding dominators via disjoint set union ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ A simpler and more efficient algorithm for the next-to-shortest path problem ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ A simplified algorithm computing all \(s-t\) bridges and articulation points ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Two flow network simplification algorithms ⋮ Computing the 2-blocks of directed graphs ⋮ Computing 2-twinless blocks ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem ⋮ Safety in \(s\)-\(t\) paths, trails and walks

This page was built for publication: Dominators in Linear Time