Finding Disjoint Paths on Directed Acyclic Graphs
Finding Disjoint Paths on Directed Acyclic Graphs
复制标题
在有向无环图上查找不相交路径
DOI：
10.1007/11604686_28
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Torsten Tholey
中科院分区：
文献类型：
--
作者：
Torsten Tholey
给定k + 1对顶点（s1，s2），（u1，v1），.，(uk，vk），我们证明了Suurballe和Tarjan的一个数据结构的修改版本可以在常数时间内对1 ≤l≤k的每一对（ul，vl）输出一个元组（s1，t1，s2，t2）{t1，t2} = {ul，vl}，使得如果存在这样的元组，则存在两个不相交的路径sp1，from 1 tot 1和p2，from 2 tot 2.不相交可以指顶点不相交和边不相交。作为一个应用程序，我们表明，所提出的数据结构可以用来改善以前最好的已知运行时间O（mn）的所谓的2-不相交路径问题的有向无环图O（m（log 2 +m/nn）+nlog 3 n）。在这个问题中，给定一个四个顶点的元组（s1，s2，t1，t2），我们想构造两条不相交的路径sp1，from 1 tot 1和p2，from 2 tot 2，如果这样的路径存在的话。
Givenk+ 1 pairs of vertices (s1,s2),(u1,v1),...,(uk,vk) of a directed acyclic graph, we show that a modified version of a data structure of Suurballe and Tarjan can output, for each pair (ul,vl) with 1 ≤l≤k, a tuple (s1,t1,s2,t2) with {t1,t2} = {ul,vl} in constant time such that there are two disjoint pathsp1, froms1tot1, andp2, froms2tot2, if such a tuple exists. Disjoint can mean vertex- as well as edge-disjoint. As an application we show that the presented data structure can be used to improve the previous best known running timeO(mn) for the so called 2-disjoint paths problem on directed acyclic graphs toO(m(log2 +m/nn) +nlog3n). In this problem, given a tuple (s1,s2,t1,t2) of four vertices, we want to construct two disjoint pathsp1, froms1tot1, andp2, froms2tot2, if such paths exist.