Decision algorithms for unsplittable flow and the half-disjoint paths problem
Decision algorithms for unsplittable flow and the half-disjoint paths problem
复制标题
不可分割流和半不相交路径问题的决策算法
DOI：
10.1145/276698.276867
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
J. Kleinberg
中科院分区：
文献类型：
--
作者：
J. Kleinberg
本文考虑有界不可裂流问题：给定网络中的t个端点对，其相关的实值需求在[0，41]范围内，为每一个端点对找到一条流路，使得通过任意端点的需求不超过1个单位.因此，该设置不能直接与经典的不相交路径问题的设置进行比较（当所有需求都等于1时）我们必须处理需求量为实数的连通问题，但我们施加了一个有界性限制，即每个连通最多只能消耗任一顶点容量的一半。我们的主要结果是有界不可分裂流问题的多项式时间算法。在任意图中，当终端对的数目是一个固定常数时。本文的算法在概念上比Robert，son和Seymour的不相交路径问题的相应算法简单得多，而且我们可以在多项式时间内判定非t个、连续超常数的终端对（up t，o Q（（log log n）2/15））的可路由性.我们还获得了多项式时间算法的几个自然优化问题的有界不分裂，可流问题，当终端对的数量是足够小的，和算法的情况下，平面图的更好的界限。所有的结果结转到涉及边缘能力的问题。我们的方法利用了几个基本的想法bhe罗伯特。森-西摩算法，连同一些新的算法组件。这一结果增加了越来越多的工作建议 * 康奈尔大学计算机科学系，伊萨卡纽约14863。电子邮件：ldeinber&s.comell，edu.部分由Alfred P. Sloan研究奖学金和NSF教师早期职业发展奖CCR-9701399支持。因为我们的有界性限制的版本虽然从潜在动机的角度来看通常相对温和，但可以对基本路由问题的易处理性产生非常有趣的定性影响。
We consider t.he bounded unsplittable flow problem: given t,erminal pairs in a network, with associated real-valued demands in bhe range [0, 41, find a single flow path for each pair so that no more than 1 unit of demand is routed t.hrough any vertex. Thus, the setting is not directly comparable to that, of 6he classical disjoint paths problem (when all demands are equal to 1) we must deal with connect.ions having varied, real-valued amounts of demand, but we impose the boundedness restriction t.hat each connection can consume at most half the capacity of any vertex Our main result is a polynomial-time algorithm for t,he bounded unsplittable flow problem, in an arbitrary graph, when the number of terminal pairs is a ilxed constant. Our algorithm is conceptually much simpler than Robert,son and Seymour’s corresponding algorithm for t.he disjoint paths problem witch a constant number of terminal pairs; and we can decide the routability of a non-t,rivially super-constant number of terminal pairs (up t,o Q((log log n)2/15)) in polynomial time. We also obtain polynomial-time algorithms for several natural opt.imizat$ion problems derived from the bounded unsplitt,able flow problem, when the number of terminal pairs is sufficiently small, and algorithms with better bounds for the case of planar graphs. The results all carry over to problems involving edge capacities. Our approach makes use of several of the ideas underlying bhe Robert.son-Seymour algorithm, together with some new algorithmic components. The resu1t.s add to a growing body of work suggest*Department of Computer Science, Cornell University, Ithaca NY 14863. Email: ldeinber&s.comell,edu. Supported in part by an Alfred P. Sloan Research Fellowship and by NSF Faculty Early Career Development Award CCR-9701399. ing that versions of our boundedness restriction while often relatively mild from the point of view of the underlying motivation can have very interesting qualitative effects on the tractability of basic routing problems.