O problema dos dois caminhos disjuntos
AUTOR(ES)
Maria Cecilia Motta Torres Giglio
DATA DE PUBLICAÇÃO
1991
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
ASSUNTO(S)
topologia teoria dos grafos análise combinatória
