文章基本信息

标题：Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems
本地全文：下载
作者：Zhang, Peng ; Zhao, Wenbo ; Zhu, Daming 等
期刊名称：COMPUTING AND INFORMATICS
印刷版ISSN：1335-9150
出版年度：2013
卷号：32
期号：1
页码：23-45
语种：English
出版社：COMPUTING AND INFORMATICS
摘要：Given a graph G=(V, E) and k source-sink pairs (s1, t1), …, (sk, tk) with each si, ti V, the Min-Sum Disjoint Paths problem asks to find k disjoint paths connecting all the source-sink pairs with minimized total length, while the Min-Max Disjoint Paths problem asks for k disjoint paths connecting all the source-sink pairs with minimized length of the longest path. We show that the weighted Min-Sum Disjoint Paths problem is FPNP-complete in general graphs, and the unweighted Min-Sum Disjoint Paths problem and the unweighted Min-Max Disjoint Paths problem cannot be approximated within m(m1-1) for any constant > 0 even in planar graphs, assuming P P NP, where m is the number of edges in G. We give for the first time a simple bicriteria approximation algorithm for the unweighted Min-Max Edge-Disjoint Paths problem and the weighted Min-Sum Edge-Disjoint Paths problem, wi
关键词：Disjoint paths, min-sum, min-max, computational complexity, approximation algorithms;68Q17, 68Q25, 68W25