Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/2713
Tipo: Relatório
Título: On a min-max conjecture for reducible digraphs
Autor(es)/Inventor(es): Szwarcfiter, Jayme Luiz
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.
Resumo : 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.
Palavras-chave: Grafos direcionados
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 0186
Data de publicação: 31-Jan-1986
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: 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
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
01_86_000040323.pdf905,86 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.