On a min-max conjecture for reducible digraphs

Szwarcfiter, Jayme Luiz

Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2713

Full metadata record

DC Field	Value	Language
dc.contributor.author	Szwarcfiter, Jayme Luiz	-
dc.date.accessioned	2017-08-18T14:01:21Z	-
dc.date.available	2023-12-21T03:02:47Z	-
dc.date.issued	1986-01-31	-
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.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.language	eng	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.title	On a min-max conjecture for reducible digraphs	en
dc.type	Relatório	pt_BR
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.publisher.country	Brasil	pt_BR
dc.publisher.department	Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO	pt_BR
dc.citation.issue	0186	pt_BR
dc.embargo.terms	aberto	pt_BR
Appears in Collections:	Relatórios

Files in This Item:

File	Description	Size	Format
01_86_000040323.pdf		905.86 kB	Adobe PDF	View/Open

Show simple item record Recommend this item View Statistics

Pantheon Institutional repository