Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems
Peng Zhang; School of Computer Science and Technology, Shandong University, Jinan 250101 ; Wenbo Zhao; Department of Computer Science and Engineering, University of California, San Diego, La Jolla ; Daming Zhu; School of Computer Science and Technology, Shandong University, Jinan
Computing and Informatics, Tome 31 (2013) no. 6, / Harvested from Computing and Informatics
Text on 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
Publié le : 2013-03-22
Classification:  Disjoint paths, min-sum, min-max, computational complexity, approximation algorithms,  68Q17, 68Q25, 68W25 
@article{cai1465,
     author = {Peng Zhang; School of Computer Science and Technology, Shandong University, Jinan 250101 and Wenbo Zhao; Department of Computer Science and Engineering, University of California, San Diego, La Jolla and Daming Zhu; School of Computer Science and Technology, Shandong University, Jinan},
     title = {Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems},
     journal = {Computing and Informatics},
     volume = {31},
     number = {6},
     year = {2013},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai1465}
}

Peng Zhang; School of Computer Science and Technology, Shandong University, Jinan 250101; Wenbo Zhao; Department of Computer Science and Engineering, University of California, San Diego, La Jolla; Daming Zhu; School of Computer Science and Technology, Shandong University, Jinan. Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems. Computing and Informatics, Tome 31 (2013) no. 6, . http://gdmltest.u-ga.fr/item/cai1465/