Pantheon Repositorio Institucional
Recopila, preserva y difundi la producción académica digital en todas las áreas del conocimiento.
Comprende los activos del repositorio, además de tesis y disertaciones en la UFRJ, artículos científicos, libros electrónicos, capítulos de libros y trabajos presentados en eventos para los profesores, investigadores, personal administrativo y estudiantes de maestría y doctorado.
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/11422/1548| Especie: | Relatório |
| Título : | Algoritmos para geração de dígrafos redutíveis |
| Autor(es)/Inventor(es): | Markenzon, Lilian Pires, Oswaldo Vernet de S. |
| Resumen: | 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. |
| Resumen: | 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. |
| Materia: | Algoritmos Grafos direcionados Algorithms |
| Materia CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade de producción: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| Es parte de: | Relatório Técnico NCE |
| Número: | 0491 |
| Fecha de publicación: | 31-mar-1991 |
| País de edición : | Brasil |
| Idioma de publicación: | por |
| Tipo de acceso : | Acesso Aberto |
| Citación : | 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) |
| Aparece en las colecciones: | Relatórios |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 04_91_000039899.pdf | 883.44 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.