On digraphs with a rooted tree structure
Jayme Luiz SZWARCFITER · Networks · 1985
Abstract A special class of reducible digraphs is characterized, those whose transitive reduction of the associated dag is a directed rooted tree. Polynomial time algorithms are described for the problems of recognition, isomorphism and finding minimum equivalent digraphs of this class. An approximative algorithm is also given for the general case of this last problem. The size of the approximation is always less than twice the exact solution. In addition, isomorphism of depth first search is solved as a special case of isomorphism of this class.