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/2713| Type: | Relatório |
| Title: | On a min-max conjecture for reducible digraphs |
| Author(s)/Inventor(s): | Szwarcfiter, Jayme Luiz |
| Abstract: | A. Frank e A. Gyártás (1976) conjecturaram que em um dígrato redutível D o número máximo de ciclos disjuntos em arestas é igual ao número mínimo de arestas que interceptam todos os cicIos de D. Provamos essa conjectura no caso especial em que D possui no máximo dois denominadores distintos. A prova conduz a um algoritmo polinomial para encontrar. tanto o conjunto máximo de cicIos quanto o conjunto mínimo de arestas, no caso considerado. |
| Abstract: | A. Frank and A. Gyárfás (1976) have conjectured that in a reducible digraph D the maximum number of edge disjoint cycles equals the minimum number of edges intersecting all cycles of D. We prove this conjecture in the special case when D has at most two distinctdominators. The proof leads to a polynomial time algorithm for finding both the maximum set of cycles and minimum set of edges, in the considered case. |
| Keywords: | Grafos direcionados |
| Subject CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO |
| Production unit: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| In: | Relatório Técnico NCE |
| Issue: | 0186 |
| Issue Date: | 31-Jan-1986 |
| Publisher country: | Brasil |
| Language: | eng |
| Right access: | Acesso Aberto |
| Citation: | SZWARCFITER, J. L. On a min-max conjecture for reducible digraphs. Rio de Janeiro: NCE, UFRJ, 1986. 8 p. (Relatório Técnico, 01/86) |
| Appears in Collections: | Relatórios |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 01_86_000040323.pdf | 905.86 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.