Finding a minimum equivalent graph of a digraph
Silvano Martello, Paolo Toth · Networks · 1982
Abstract The problem considered is that of removing the maximum number of edges from a digraph without affecting its reachability properties. The worst‐case performance of algorithms from the related literature is analyzed; it is found that Hsu's method contains some mistakes. A new algorithm is presented, based on a reduction procedure and on a branch and bound search; its efficiency is studied both theoretically and through computational experiments.