Dominator Tree Certification and Divergent Spanning Trees
From MaRDI portal
Publication:4962208
DOI10.1145/2764913zbMath1398.68396arXiv1210.8303OpenAlexW2242691822MaRDI QIDQ4962208
Loukas Georgiadis, Robert Endre Tarjan
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1210.8303
dominatorsconnectivitydirected graphdepth-first searchflow graphglobal code optimizationprogram certificationdynamic list
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (10)
A Fast Verified Liveness Analysis in SSA Form ⋮ 2-Vertex Connectivity in Directed Graphs ⋮ Minimum 2-vertex strongly biconnected spanning directed subgraph problem ⋮ 2-vertex connectivity in directed graphs ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Efficient computation of arbitrary control dependencies ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Dynamic Dominators and Low-High Orders in DAGs
This page was built for publication: Dominator Tree Certification and Divergent Spanning Trees
