Finding dominators via disjoint set union

DOI10.1016/j.jda.2013.10.003zbMath1294.05148arXiv1310.2118MaRDI QIDQ396673

Mohammad Hasan, H. S. Yoon

Publication date: 13 August 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.2118

zbMATH Keywords

dominators; directed graph; depth-first search; disjoint set union; flow graph; global code optimization; program certification

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68P05: Data structures

05C20: Directed graphs (digraphs), tournaments