Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems
Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems
复制标题
3 跳和 4 跳有界不相交路径问题的逼近性
DOI：
10.1007/978-3-642-13036-6_16
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
José Neto
中科院分区：
文献类型：
--
作者：
A. Bley;José Neto
如果一条路径至多包含两条边，则称它是有界的.我们考虑两类有界不交路问题。在最大边或结点不交路问题MEDP（n）和MNDP（n）中，任务是在给定的图G中分别求出最大数目的边或结点不交的有界（s，t）路.在加权边或结点不交路问题WEDP（n）和WNDP（n）中，我们也给出了一个整数k ∈ n和非负的边权ce ∈ n，e∈E，并求G的一个最小权子图，其中包含边或结点不交的有界（s，t）路.这两个问题在容错通信网络的规划中有很大的实际意义，例如，尽管在过去的几十年里，长度有界的割流问题已经得到了深入的研究，但一些3-和4-有界不相交路径问题的难度仍然是开放的。本文讨论了所有开放情形的复杂性状态，证明了WNDP（3）可以在多项式时间内求解，MEDP（4）是-完全的和在因子2内可逼近的，WNDP（4）和WEDP（4）分别是-困难的和-完全的.
A path is said to be ℓ-bounded if it contains at most ℓ edges. We consider two types of ℓ-bounded disjoint paths problems. In the maximum edge- or node-disjoint path problems MEDP(ℓ) and MNDP(ℓ), the task is to find the maximum number of edge- or node-disjoint ℓ-bounded (s,t)-paths in a given graphGwith sourcesand sinkt, respectively. In the weighted edge- or node-disjoint path problems WEDP(ℓ) and WNDP(ℓ), we are also given an integerk∈ ℕ and non-negative edge weightsce∈ ℕ,e∈E, and seek for a minimum weight subgraph ofGthat containskedge- or node-disjoint ℓ-bounded (s,t)-paths. Both problems are of great practical relevance in the planning of fault-tolerant communication networks, for example.Even though length-bounded cut and flow problems have been studied intensively in the last decades, the-hardness of some 3- and 4-bounded disjoint paths problems was still open. In this paper, we settle the complexity status of all open cases showing that WNDP(3) can be solved in polynomial time, that MEDP(4) is-complete and approximable within a factor of 2, and that WNDP(4) and WEDP(4) are-hard and-complete, respectively.