Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1548
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMarkenzon, Lilian-
dc.contributor.authorPires, Oswaldo Vernet de S.-
dc.date.accessioned2017-03-14T13:23:51Z-
dc.date.available2017-03-16T03:00:14Z-
dc.date.issued1991-03-31-
dc.identifier.citationMARKENZON, L.; VERNET, O. Algoritmos para geração de dígrafos redutíveis. Rio de Janeiro: NCE, UFRJ, 1991. 16 p. (Relatório Técnico, 04/91)pt_BR
dc.identifier.urihttp://hdl.handle.net/11422/1548-
dc.description.abstractThis Technical Report describes four algorithmsfor the reducible flow graphs generation. We characterize at first this class of digraphs, enunciating their mais properties and Tarjan's recognition alorithm. We propose two methods for the random eneration: the first one is a slight variant of the reducibility test applied on a digraph randomly generated, deleting the edges which violate the reducibility criteria: the second one, uses a post-order traversal of a partitioning tree. Finally, the subclass of complete (or saturated) reducible flow graphs is also characterized, including two distinct methods for its generation.en
dc.languageporpt_BR
dc.relation.ispartofRelatório Técnico NCEpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgoritmospt_BR
dc.subjectGrafos direcionadospt_BR
dc.subjectAlgorithmsen
dc.titleAlgoritmos para geração de dígrafos redutíveispt_BR
dc.typeRelatóriopt_BR
dc.description.resumoEste Relatório Técnico descreve quatro algoritmos para geração de dígrafos redutíveis. De início, caracterizamos esta família de dígrafos, enunciando algumas de suas principais propriedades e o algoritmo de Tarjan par o seu reconhecimento. Propomos dois métodos para geração randômica: o primeiro deles decorre da imediata aplicação do teste de redutibilidade sobre um dígrafo gerado aleatoriamente, no sentido de eliminar arestas que o tornem não redutível: o segundo utiliza um percurso em pós-ordem de uma árvore de particionamento. Caracterizamos, finalmente, uma sub-classe dos dígrafos redutíveis, denominados completos ou saturados, e mostramos duas maneiras distintas de gerá-los.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.issue0491pt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Relatórios

Files in This Item:
File Description SizeFormat 
04_91_000039899.pdf883.44 kBAdobe PDFView/Open


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