Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1515
Tipo: Relatório
Título: On digraphs with a rooted tree structure
Autor(es)/Inventor(es): Szwarcfiter, Jayme Luiz
Resumo: 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.
Resumo : 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.
Palavras-chave: Teoria dos grafos
Grafos direcionados
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 0483
Data de publicação: 31-Dez-1983
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: 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
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
04-83_000040316.pdf307,31 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.