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
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
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