A fast algorithm for finding dominators in a flowgraph
From MaRDI portal
Publication:3896499
DOI10.1145/357062.357071zbMath0449.68024OpenAlexW2111379929WikidataQ55934256 ScholiaQ55934256MaRDI QIDQ3896499
Thomas Lengauer, Robert Endre Tarjan
Publication date: 1979
Published in: ACM Transactions on Programming Languages and Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/357062.357071
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Strong articulation points and strong bridges in large scale graphs, Efficient symbolic analysis of programs, Encoding and constructing 1-nested phylogenetic networks with trinets, Optimal register allocation for SSA-form programs in polynomial time, 2-vertex connectivity in directed graphs, Phylogenetic diversity and biodiversity indices on phylogenetic networks, A min-max relation in flowgraphs, Efficient static checker for tainted variable attacks, Dynamic program slicing, Finding dominators via disjoint set union, Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions, Hybrid information flow control for low-level code, An efficient customized clock allocation algorithm for a class of timed automata, Strong Connectivity in Directed Graphs under Failures, with Applications, Efficient computation of arbitrary control dependencies, On 2-strong connectivity orientations of mixed graphs and related problems, Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal, Doomed program points, A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems, Efficient parallel algorithms for path problems in directed graphs, Generalized dominators, Probabilistic verification of Boolean functions, A \(\min\)-\(\max\) relation in flowgraphs and some applications, Mechanized Verification of Computing Dominators for Formalizing Compilers, Criticality: static profiling for real-time programs, Generalized dominators for structured programs, A decomposition theorem and two algorithms for reticulation-visible networks, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph, Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning, Dynamic Dominators and Low-High Orders in DAGs, Combining tree partitioning, precedence, and incomparability constraints, Efficient Computation of Dominance in Component Systems (Short Paper), A uniform approach to semi-dynamic problems on digraphs, An approach for extracting a small unsatisfiable core, Computing the 2-blocks of directed graphs, Sparse Weight Tolerant Subgraph for Single Source Shortest Path, An \(O(| V|^*| E|)\) algorithm for finding immediate multiple-vertex dominators, Computing 2-twinless blocks, A linear-time algorithm for a special case of disjoint set union
