On the maximum disjoint paths problem on edge-colored graphs

作     者：Wu, Bang Ye 

作者机构：Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2012年第9卷第1期

页      面：50-57页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：National Science Council  Taiwan  ROC [NSC 97-2221-E-194-064-MY3  NSC 98-2221-E-194-027-MY3] 

主　　题：Algorithm Approximation algorithm Colored-graph Disjoint paths Social network analysis Connectivity 

摘      要：We study the problem of finding the maximum number of disjoint uni-color paths in an edge-colored graph. We show the NP-hardness and the approximability and present approximation and exact algorithms. We also study the length-bounded version of the problem, in which the numbers of edges of the found paths are required to be upper bounded by a fixed integerl I. lt is shown that the problem can be solved in polynomial time for I = 4. We also show that the problem can be approximated with ratio (I-1)/2 + epsilon in polynomial time for any epsilon 0. Particularly, for I = 4, we present an efficient 2-approximation algorithm. (C) 2012 Elsevier B.V. All rights reserved.