Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGuo, L.en
dc.contributor.authorShen, H.en
dc.contributor.authorLiao, K.en
dc.contributor.authorLi, P.en
dc.identifier.citationProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, 2015 / vol.2015-June, pp.62-64en
dc.description.abstractLet G = (V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D ∈ Z+ 0 be a delay bound, the k disjoint Restricted Shortest Path (kRSP) problem is to compute k disjoint paths between s and t with the total cost minimized and the total delay bounded by D. In this paper, we first present a pseudo- polynomial-time algorithm with a bifactor approximation ratio of (1, 2), then improve the algorithm to polynomial time with a bifactor ratio of (1+∈, 2+∈) for any fixed ǫ > 0, which is better than the current best approximation ratio (O(1 + γ),O(1 + ln ¹ )) for any fixed γ > 0 [3, 5]. To the best of our knowledge, this is the first constant-factor algo- rithm that almost strictly obeys kRSP constraint.en
dc.description.statementofresponsibilityLongkun Guo, Kewen Liaoen
dc.rightsCopyright is held by the owner/author(s). Publication rights licensed to ACMen
dc.subjectk Disjoint Restricted Shortest Path; Bifactor Approximation Algorithm; Auxiliary Graph; Cycle Cancellation.en
dc.titleBrief announcement: efficient approximation algorithms for computing k disjoint restricted shortest pathsen
dc.typeConference paperen
dc.contributor.conference27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA) (13 Jun 2015 - 15 Jun 2015 : Portland, OR)en
pubs.library.collectionComputer Science publicationsen
dc.identifier.orcidShen, H. [0000-0002-3663-6591]en
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_108585.pdfRestricted Access334.92 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.