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

DOI10.1137/070693217MaRDI QIDQ3395044zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

analysis of algorithmsdata structuresinterval analysispointer machineminimum spanning treesflowgraphsset unionpath compressionrandom-access machinenearest common ancestorscomponent treefinding dominators

Mathematics Subject Classification ID

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)

Recommendations

• Finding dominators revisited (extended abstract)
• scientific article; zbMATH DE number 1775413
• Finding dominators via disjoint set union
• Algorithms – ESA 2004
• Finding Dominators in Practice

Cited in

(31)

• Finding dominators via disjoint set union
• On computing the 2-vertex-connected components of directed graphs
• Algorithms – ESA 2004
• Finding strong bridges and strong articulation points in linear time
• Succinct indices for path minimum, with applications
• Strong articulation points and strong bridges in large scale graphs
• On the graph traversal method for evaluating linear binary-chain programs
• Computing the 2-blocks of directed graphs
• Safety in \(s\)-\(t\) paths, trails and walks
• Efficient computation of arbitrary control dependencies
• scientific article; zbMATH DE number 1775413 (Why is no real title available?)
• 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)
• Sparse certificates for 2-connectivity in directed graphs
• Computing 2-twinless blocks
• Fault-tolerant subgraph for single-source reachability: general and optimal
• Strong connectivity in directed graphs under failures, with applications
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
• 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)