Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11422/1515| Type: | Relatório |
| Title: | On digraphs with a rooted tree structure |
| Author(s)/Inventor(s): | Szwarcfiter, Jayme Luiz |
| Abstract: | 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. |
| Abstract: | 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. |
| Keywords: | Teoria dos grafos Grafos direcionados |
| Subject CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Production unit: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| In: | Relatório Técnico NCE |
| Issue: | 0483 |
| Issue Date: | 31-Dec-1983 |
| Publisher country: | Brasil |
| Language: | eng |
| Right access: | Acesso Aberto |
| Citation: | SZWARCFITER, J. L. On digraphs with a rooted tree structure. Rio de Janeiro: NCE, UFRJ, 1983. 12 p. (Relatório Técnico, 04/83) |
| Appears in Collections: | Relatórios |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 04-83_000040316.pdf | 307.31 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.