Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1515
Type: Relatório
Title: On digraphs with a rooted tree structure
Author(s)/Inventor(s): Szwarcfiter, Jayme Luiz
Abstract: 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.
Abstract: 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.
Keywords: Teoria dos grafos
Grafos direcionados
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 0483
Issue Date: 31-Dec-1983
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: SZWARCFITER, J. L. On digraphs with a rooted tree structure. Rio de Janeiro: NCE, UFRJ, 1983. 12 p. (Relatório Técnico, 04/83)
URI: http://hdl.handle.net/11422/1515
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
04-83_000040316.pdf307,31 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.