The Transitive Reduction of a Directed Graph
1972; Society for Industrial and Applied Mathematics; Volume: 1; Issue: 2 Linguagem: Inglês
10.1137/0201008
ISSN1095-7111
AutoresAlfred V. Aho, M. R. Garey, Jeffrey D. Ullman,
Tópico(s)Cellular Automata and Applications
ResumoWe consider economical representations for the path information in a directed graph. A directed graph $G^t $ is said to be a transitive reduction of the directed graph G provided that (i) $G^t $ 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 $G^t $ 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.
Referência(s)