Algoritmos para geração de dígrafos redutíveis

Markenzon, Lilian; Pires, Oswaldo Vernet de S.

Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1548

Full metadata record

DC Field	Value	Language
dc.contributor.author	Markenzon, Lilian	-
dc.contributor.author	Pires, Oswaldo Vernet de S.	-
dc.date.accessioned	2017-03-14T13:23:51Z	-
dc.date.available	2023-12-21T03:02:48Z	-
dc.date.issued	1991-03-31	-
dc.identifier.citation	MARKENZON, 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.uri	http://hdl.handle.net/11422/1548	-
dc.description.abstract	This 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.language	por	pt_BR
dc.relation.ispartof	Relatório Técnico NCE	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Algoritmos	pt_BR
dc.subject	Grafos direcionados	pt_BR
dc.subject	Algorithms	en
dc.title	Algoritmos para geração de dígrafos redutíveis	pt_BR
dc.type	Relatório	pt_BR
dc.description.resumo	Este 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.country	Brasil	pt_BR
dc.publisher.department	Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	pt_BR
dc.citation.issue	0491	pt_BR
dc.embargo.terms	aberto	pt_BR
Appears in Collections:	Relatórios

Files in This Item:

File	Description	Size	Format
04_91_000039899.pdf		883.44 kB	Adobe PDF	View/Open

Show simple item record Recommend this item View Statistics

Pantheon Institutional repository