1. Pantheon
  2. Trabalhos Acadêmicos e Técnicos
  3. Relatórios Técnicos e de Pesquisa
  4. Relatórios
Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1515
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSzwarcfiter, Jayme Luiz-
dc.date.accessioned2017-03-08T17:32:32Z-
dc.date.available2023-12-21T03:02:45Z-
dc.date.issued1983-12-31-
dc.identifier.citationSZWARCFITER, J. L. On digraphs with a rooted tree structure. Rio de Janeiro: NCE, UFRJ, 1983. 12 p. (Relatório Técnico, 04/83)pt_BR
dc.identifier.urihttp://hdl.handle.net/11422/1515-
dc.description.abstractA 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.pt_BR
dc.languageengpt_BR
dc.relation.ispartofRelatório Técnico NCEpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectGrafos direcionadospt_BR
dc.titleOn digraphs with a rooted tree structurept_BR
dc.typeRelatóriopt_BR
dc.description.resumoUma 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.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto Tércio Pacitti de Aplicações e Pesquisas Computacionaispt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
dc.citation.issue0483pt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Relatórios

Files in This Item:
File Description SizeFormat 
04-83_000040316.pdf307.31 kBAdobe PDFView/Open
Show simple item record Recommend this item View Statistics


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