Orientador: Claudio L. Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-13T23:27:26Z (GMT). No. of bitstreams: 1
Giglio_MariaCeciliaMottaTorres_M.pdf: 5819263 bytes, checksum: c24dd7357f8a2283359356720f51597b (MD5)
Previous issue date: 1990 / 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. / Mestrado / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275866 |
| Date | 17 January 1991 |
| Creators | Giglio, Maria Cecilia Motta Torres |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Lucchesi, Cláudio Leonardo, 1945-, Lucchesi, Claudio L. |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Ciência da Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 64f. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds