Please use this identifier to cite or link to this item:
http://hdl.handle.net/2440/95766
Citations  
Scopus  Web of Science®  Altmetric 

?

?

Full metadata record
DC Field  Value  Language 

dc.contributor.author  Guo, L.  en 
dc.contributor.author  Shen, H.  en 
dc.contributor.author  Liao, K.  en 
dc.date.issued  2015  en 
dc.identifier.citation  Journal of Combinatorial Optimization, 2015; 29(1):153164  en 
dc.identifier.issn  13826905  en 
dc.identifier.issn  15732886  en 
dc.identifier.uri  http://hdl.handle.net/2440/95766   
dc.description.abstract  For a given graph G with distinct vertices s and t, nonnegative integral cost and delay on edges, and positive integral boundC and D on cost and delay respectively, the k biconstraint path (kBCP) problem is to compute k disjoint stpaths subject to C and D. This problem is known to be NPhard, even when k = 1 (Garey and Johnson, Computers and Intractability, 1979 ). This paper first gives a simple approximation algorithm with factor(2, 2), i.e. the algorithm computes a solution with delay and cost bounded by 2 ∗ D and 2 ∗ C respectively. Later, a novel improved approximation algorithm with ratio (1 + β, max{2, 1 + ln(1/β)}) is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor(1.369, 2) approximation algorithm immediately and a factor(1.567, 1.567) algorithm by slightly modifying the algorithm. Besides, when β = 0, the algorithm is shown to be with ratio (1, O(ln n)), i.e. it is an algorithm with only a single factor ratio O(ln n) on cost. To the best of our knowledge, this is the first nontrivial approximation algorithm that strictly obeys the delay constraint for the kBCP problem.  en 
dc.description.statementofresponsibility  Longkun Guo, Hong Shen, Kewen Lia  en 
dc.language.iso  en  en 
dc.publisher  SPRINGER  en 
dc.rights  © Springer Science+Business Media New York 2013  en 
dc.subject  kdisjoint biconstraint path; NPhard; Bifactor approximation algorithm; Auxiliary graph; Cycle cancellation  en 
dc.title  Improved approximation algorithms for computing k disjoint paths subject to two constraints  en 
dc.type  Journal article  en 
dc.identifier.rmid  0030023957  en 
dc.identifier.doi  10.1007/s108780139693x  en 
dc.identifier.pubid  71424   
pubs.library.collection  Computer Science publications  en 
pubs.library.team  DS07  en 
pubs.verificationstatus  Verified  en 
pubs.publicationstatus  Published  en 
dc.identifier.orcid  Shen, H. [0000000236636591]  en 
Appears in Collections:  Computer Science publications 
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.