Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2712
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSzwarcfiter, Jayme Luiz-
dc.date.accessioned2017-08-18T13:57:33Z-
dc.date.available2017-08-20T03:00:23Z-
dc.date.issued1987-04-30-
dc.identifier.citationSZWARCFITER, J. L. On minimum cuts of cycles by vertices and vertex disjoint cycles. Rio de Janeiro: NCE, UFRJ, 1987. 21 p. (Relatório Técnico, 02/87)pt_BR
dc.identifier.urihttp://hdl.handle.net/11422/2712-
dc.description.abstractWe describe a new family of di.graphs, named connectively reducible, for which we prove that the minimum cardinality of a set of vertices intersecting all cycles equals the maximum cardinality of a set of vertex disjoint cycles. In.addltion, formulate polynomial time algorithms for the problems of recognition and finding these minimum and maxium sets for digraphs of the family. Similar results hold for the currently existing families of fully reducible and cyclically reducible digraphs. Neither the fully reducible are contained nor contain the cyclically reducible. However, we show that the connectively reducible digraphs contain both of the existing families.en
dc.languageengpt_BR
dc.relation.ispartofRelatório Técnico NCEpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectAlgoritmospt_BR
dc.subjectGraphs theoryen
dc.subjectAlgorithmsen
dc.titleOn minimum cuts of cycles by vertices and vertex disjoint cyclesen
dc.typeRelatóriopt_BR
dc.description.resumoDescrevemos uma nova família de dígrafos, denominados conexamente redutíveis, para a qual provamos que, a cardinalidade mínima de um conjunto de vértices que interceptam todos os ciclos iguala à máxima de um conjunto de ciclos disjuntos em vértices. Além disso, formulamos algoritmos polinomiais para os prpblemas de reconhecimento e determinação desses conjuntos, mínimo e máximo, para dígrafos dessa família. Resultados similares são conhecidos para os dígrafos totalmente redutíveis. Mais recentemente, uma outra família foi definida, os dígrafos ciclicamente redutíveis, que também possibilita a computação em tempo polinomial desses conjuntos mínimo e máximo. E conhecido o fato de que os dígrafos totalmente redutíveis não estão contidos nem contêm os ciclicamente redutíveis. Em contraste, provamos que os conexamente redutíveis, contêm ambas as famílias existentes.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto Tércio Pacitti de Aplicações e Pesquisas Computacionaispt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAOpt_BR
dc.citation.issue0287pt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
02_87_000040328.pdf802,07 kBAdobe PDFView/Open


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