Relatório
On digraphs with a rooted tree structure
Registro en:
SZWARCFITER, J. L. On digraphs with a rooted tree structure. Rio de Janeiro: NCE, UFRJ, 1983. 12 p. (Relatório Técnico, 04/83)
Autor
Szwarcfiter, Jayme Luiz
Institución
Resumen
A special class of reducible digraphs is characterized and polynomial time algorithms are described for their recognition, isomorphism and finding minimum equivalent digraphs. An approximative algorithm is also given for solving this last problem in this general case. The size of the approximation is always less thantwice the exact solution. In addition, isomorphism of depht first search is solved as a special case of isomorphism of this class. Uma classe especial de diagrafos redutíveis é caracterizada e algoritmos polinomiais são descritos para o seu reconhecimento, isomorfismo e determinar digrafos equivalentes mínimos. Um algorítmo aproximativo é também apresentado para resolver este último problema, em seu caso geral. O tamanho da aproximação obtida é sempre menor do que o dobro da solução exata. Em adição, o isomorfismo de busca em profundidade é resolvido como um caso especial do isomorfismo dessa classe.