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
Department : 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)
URI: http://hdl.handle.net/11422/2713
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
01_86_000040323.pdf905,86 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.