Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/81883
Type: Artigo de periódico
Title: On the connection between the undirected and the Acyclic Directed Two Disjoint Paths Problem
Author: Lucchesi, CL
Giglio, MCMT
Abstract: Given an undirected graph G and four distinct special vertices s(1),s(2),t(1),t(2), the Undirected Two Disjoint Paths Problem consists in determining whether there are two disjoint paths connecting s(1) to t(1) and s(2) to t(2), respectively. There is an analogous version of the problem for acyclic directed graphs, in which it is required that the two paths be directed, as well. The well known characterizations for the nonexistence of solutions in both problems are, in some sense, the same, which indicates that under some weak conditions the edge orientations in the directed version are irrelevant. We present the first direct proof of the irrelevance of edge orientations.
Country: Canadá
Editor: Charles Babbage Res Ctr
Rights: fechado
Date Issue: 1997
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


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