1972/06/01 by Alfred V. Aho, M. R. Garey, Jeffrey D. Ullman · 723 citations
Computer Science · Engineering · Mathematics · #Computability, Logic, AI Algorithms #Scheduling and Optimization Algorithms #Cellular Automata and Applications #Transitive reduction #Combinatorics #Transitive closure #Mathematics #Directed graph #Discrete mathematics #Vertex (graph theory) #Regular graph #Null graph #Transitive relation #Graph #Voltage graph #Line graph
paper · doi:10.1137/0201008
published in SIAM Journal on Computing 1(2), 131-137 (Society for Industrial and Applied Mathematics)
openalex publication_date 1972/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
We consider economical representations for the path information in a directed graph. A directed graph Gt is said to be a transitive reduction of the directed graph G provided that (i) Gt has a directed path from vertex u to vertex v if and only if G has a directed path from vertex u to vertex v, and (ii) there is no graph with fewer arcs than Gt satisfying condition (i). Though directed graphs with cycles may have more than one such representation, we select a natural canonical representative as the transitive reduction for such graphs. It is shown that the time complexity of the best algorithm for finding the transitive reduction of a graph is the same as the time to compute the transitive closure of a graph or to perform Boolean matrix multiplication.