| dc.creator | Szwarcfiter, Jayme Luiz | |
| dc.date | 2017-08-18T14:01:21Z | |
| dc.date | 2023-09-27T03:01:19Z | |
| dc.date | 1986-01-31 | |
| dc.date.accessioned | 2023-09-27T13:10:05Z | |
| dc.date.available | 2023-09-27T13:10:05Z | |
| dc.identifier | 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) | |
| dc.identifier | http://hdl.handle.net/11422/2713 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/8902363 | |
| dc.description | 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. | |
| dc.description | 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. | |
| dc.language | eng | |
| dc.publisher | Brasil | |
| dc.publisher | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais | |
| dc.relation | Relatório Técnico NCE | |
| dc.rights | Acesso Aberto | |
| dc.subject | Grafos direcionados | |
| dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO | |
| dc.title | On a min-max conjecture for reducible digraphs | |
| dc.type | Relatório | |
