Premium
On digraphs with a rooted tree structure
Author(s) -
Szwarcfiter Jayme L.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150106
Subject(s) - isomorphism (crystallography) , mathematics , digraph , reduction (mathematics) , combinatorics , class (philosophy) , subgraph isomorphism problem , graph isomorphism , time complexity , tree (set theory) , transitive relation , discrete mathematics , polynomial , search tree , algorithm , computer science , search algorithm , graph , artificial intelligence , mathematical analysis , chemistry , geometry , line graph , crystal structure , crystallography
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.