On a min-max conjecture for reducible digraphs
| dc.citation.issue | 0186 | pt_BR |
| dc.creator | Szwarcfiter, Jayme Luiz | |
| dc.date.accessioned | 2017-08-18T14:01:21Z | |
| dc.date.available | 2026-05-16T03:03:30Z | |
| dc.date.issued | 1986-01-31 | |
| dc.description.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. | en |
| dc.description.resumo | 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. | pt_BR |
| dc.embargo.terms | aberto | pt_BR |
| dc.identifier.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) | pt_BR |
| dc.identifier.uri | http://hdl.handle.net/11422/2713 | |
| 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 | Grafos direcionados | pt_BR |
| dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO | pt_BR |
| dc.title | On a min-max conjecture for reducible digraphs | en |
| dc.type | Relatório | pt_BR |