Testing flow graph reducibility

DOI10.1016/S0022-0000(74)80049-8zbMath0315.68018OpenAlexW2146441023MaRDI QIDQ1221484

Robert Endre Tarjan

Publication date: 1974

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(74)80049-8

Mathematics Subject Classification ID

General topics in the theory of software (68N01)

Related Items

On digraphs with a rooted tree structure, Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT, Packing feedback arc sets in reducible flow graphs, Notes on oriented depth-first search and longest paths, Full characterization of a class of graphs tailored for software watermarking, Finding dominators via disjoint set union, On the resilience of canonical reducible permutation graphs, Properties of data flow frameworks: A unified model, Flow hypergraph reducibility, Program derivation with verified transformations — a case study, COMPILE-TIME ANALYSIS AND OPTIMIZATION OF EXPLICITLY PARALLEL PROGRAMS*, Efficient parallel algorithms for path problems in directed graphs, Edge-disjoint spanning trees and depth-first search, A generalized mathematical theory of structured programming, Node listings for reducible flow graphs, Dynamic Dominators and Low-High Orders in DAGs, Modelling and programming stream-based distributed computing based on the meta-pipeline approach, A linear-time algorithm for a special case of disjoint set union

Cites Work

• Fast algorithms for the elimination of common subexpressions
• Finding Dominators in Directed Graphs
• Characterizations of Reducible Flow Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficiency of Equivalence Algorithms
• Depth-First Search and Linear Graph Algorithms
• Set Merging Algorithms
• A global flow analysis algorithm
• Flow Graph Reducibility
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item