The disjoint paths problem in quadratic time
The disjoint paths problem in quadratic time
复制标题
DOI：
10.1016/j.jctb.2011.07.004
复制
发表时间：
2012-03-01
影响因子：
1.4
通讯作者：
Reed, Bruce
中科院分区：
文献类型：
--
作者：
Kawarabayashi, Ken-ichi;Kobayashi, Yusuke;Reed, Bruce
我们考虑以下众所周知的问题，这被称为不相交路径问题。对于一个给定的图G和G中的一组k对终端，目标是找到连接给定终端对的k条顶点不相交的路，或者得出这样的路不存在的结论。对于固定的k，我们为该问题提出了一个O（n（2））时间算法。这改进了Robertson和Seymour的开创性结果的时间复杂度，他们给出了固定k的不相交路径问题的O（n（3））时间算法。注意Perkovic和Reed（2000）在[24]中宣布（没有证明）这个问题可以在O（n（2））时间内解决。我们的算法意味着有一个O（n（2））的时间算法的k边不相交的路径问题，次要的包容问题，和标记次要的包容问题。实际上，所有算法的时间复杂度都可以提高到O（n（2）），其中最昂贵的部分取决于Robertson和Seymour算法，例如，图的次闭类的成员测试。(C)2011 Elsevier Inc. All rights reserved.
We consider the following well-known problem, which is called the disjoint paths problem. For a given graph G and a set of k pairs of terminals in G, the objective is to find k vertex-disjoint paths connecting given pairs of terminals or to conclude that such paths do not exist. We present an O(n(2)) time algorithm for this problem for fixed k. This improves the time complexity of the seminal result by Robertson and Seymour, who gave an O(n(3)) time algorithm for the disjoint paths problem for fixed k. Note that Perkovic and Reed (2000) announced in [24] (without proofs) that this problem can be solved in O(n(2)) time. Our algorithm implies that there is an O(n(2)) time algorithm for the k edge-disjoint paths problem, the minor containment problem, and the labeled minor containment problem. In fact, the time complexity of all the algorithms with the most expensive part depending on Robertson and Seymour's algorithm can be improved to O(n(2)), for example, the membership testing for minor-closed class of graphs. (C) 2011 Elsevier Inc. All rights reserved.