An Algorithm for Finding a Minimal Equivalent Graph of a Digraph
Harry T. Hsu · Journal of the ACM · 1975
It lS found that Moyles and Thompson's algorithm contains some mistakes.An efficmnt algorLthm for finding a mlmmal eqmvalent graph (MEG) is presented The algorithm proceeds with the following steps First, all the strongly connected (s c ) components are found.Then the set of vertmes is reordered such that the set of vertices in an s c component is ordered by consecutive integers The rows and columns of the adjacency matrix are permuted accordingly Then an MEG for each s c. component is found Finally, the parallel and the superfluous edges are removed KEY WORDS AND PHRASES' digraph, algorithm, minimal equivalent graph, adjacency matrix, acychc digraph, condensed digraph CR CATLGORILS' 5 32 PrelzminariesLet G = (V, E) be a digraph, where V as the set of all the vertices where [ V I = N, and E is the set of all the edges in G, where I E I = M.For M1 vertices v, and v~ of G, if there is an elementary path from v, to v~, it is said that v, R v~.All the paths in this paper refer to elementary directed paths.An s.c.digraph is one such that for all v, and v~ E V, v, R vj and v, R re.An acyclic digraph is one such that if v, R v,, then vj,R v,.An acyclic digraph contains no cycles.The following defines an MEG of a digraph.