On digraphs with a rooted tree structure
| dc.citation.issue | 0483 | pt_BR |
| dc.creator | Szwarcfiter, Jayme Luiz | |
| dc.date.accessioned | 2017-03-08T17:32:32Z | |
| dc.date.available | 2026-05-16T03:03:29Z | |
| dc.date.issued | 1983-12-31 | |
| dc.description.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. | pt_BR |
| dc.description.resumo | 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. | pt_BR |
| dc.embargo.terms | aberto | pt_BR |
| dc.identifier.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) | pt_BR |
| dc.identifier.uri | http://hdl.handle.net/11422/1515 | |
| dc.language | eng | pt_BR |
| dc.publisher.country | Brasil | pt_BR |
| dc.publisher.department | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais | pt_BR |
| dc.relation.ispartof | Relatório Técnico NCE | pt_BR |
| dc.rights | Acesso Aberto | pt_BR |
| dc.subject | Teoria dos grafos | pt_BR |
| dc.subject | Grafos direcionados | pt_BR |
| dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | pt_BR |
| dc.title | On digraphs with a rooted tree structure | pt_BR |
| dc.type | Relatório | pt_BR |