• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Guo, L. (Guo, L..) [1] | Shen, H. (Shen, H..) [2] | Liao, K. (Liao, K..) [3] | Li, P. (Li, P..) [4]

Indexed by:

Scopus

Abstract:

Let G = (V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D ∈ ℤ+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 pseudopolynomial-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 + ln1/γ)) for any fixed γ > 0 [3, 5]. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint. Copyright © 2015 ACM.

Keyword:

Auxiliary graph; Bifactor approximation algorithm; Cycle cancellation; K disjoint restricted shortest path

Community:

  • [ 1 ] [Guo, L.]School of Mathematics and Computer Science, Fuzhou University, China
  • [ 2 ] [Shen, H.]School of Computer Science, University of Adelaide, Australia
  • [ 3 ] [Liao, K.]Dept. of Computing and Information Systems, University of Melbourne, Australia
  • [ 4 ] [Li, P.]Dept. of Computer Science and Engineering, Washington University, St. Louis, United States

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Annual ACM Symposium on Parallelism in Algorithms and Architectures

Year: 2015

Volume: 2015-June

Page: 62-64

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 9

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:236/10278776
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1