Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||On the connection between the undirected and the Acyclic Directed Two Disjoint Paths Problem|
|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.|
|Editor:||Charles Babbage Res Ctr|
|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.