Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275866
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: O problema dos dois caminhos disjuntos
Author: Giglio, Maria Cecilia Motta Torres
Advisor: Lucchesi, Cláudio Leonardo, 1945-
Lucchesi, Claudio L.
Abstract: Resumo: O problema dos dois caminhos disjuntos consiste em determinar, dados vértices s1, S2, t1 e t2 de um grafo, se existem ou não dois caminhos disjuntos, P1 e P2 ligando s1 a t1 e S1 a t1, respectivamente. O problema se manifesta em quatro versões, a saber, o grafo pode ser orientado ou não, e a exigência de disjunção pode ser apenas nas arestas ou também nos vértices. Nas quatro versões, o problema admite reduções elementares do ponto de vista computacional que levam finalmente à solução ou a uma certidão da sua não existência. Esta análise apresenta uma interconexão interessante entre combinatória, complexidade de algoritmos e topologia. No caso de grafos orientados, exige-se também que o grafo seja acíclico, pois caso contrário o problema se torna NP-difícil.

Abstract: The two disjoint paths problem consists in determining, given vertices S1, S2, t1 and t2 of a graph, whether or not there exist two disjoint paths. P1 and P21 joining s1 to t1 and S2 to t2 respectively. The problem may be considered in four versions, namely, the graph may or may not be directed, and the disjointness requirement on the paths may be on the edges only or on the vertices too. In all version, the problem admits computationally elementary reductions which provide either a solution or a certificate of its nonexistence. The analysis presents an interesting interconnection between combinatorics, complexity of algorithms and topology. In the case of direct graphs, it is also required that the graph be acyclic, otherwise the problem becomes NP-hard.
Subject: Teoria dos grafos
Análise combinatória
Topologia
Language: Português
Editor: [s.n.]
Date Issue: 1990
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Giglio_MariaCeciliaMottaTorres_M.pdf5.68 MBAdobe PDFView/Open


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