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

author:

Guo, Longkun (Guo, Longkun.) [1] (Scholars:郭龙坤) | Liao, Kewen (Liao, Kewen.) [2] | Shen, Hong (Shen, Hong.) [3] | Li, Peng (Li, Peng.) [4]

Indexed by:

CPCI-S EI 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. epsilon Zeta(+) (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+ epsilon, 2+ o) for any fixed epsilon > 0, which is better than the current best approximation ratio (O (1 + gamma), O(1 + ln 1/gamma) for any fixed gamma > 0 [3, 5]. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint .

Keyword:

Auxiliary Graph Bifactor Approximation Algorithm Cycle Cancellation. k Disjoint Restricted Shortest Path

Community:

  • [ 1 ] [Guo, Longkun]Fuzhou Univ, Sch Math & Comp Sci, Fuzhou, Fujian, Peoples R China
  • [ 2 ] [Liao, Kewen]Univ Melbourne, Dept Comp & Informat Syst, Melbourne, Vic, Australia
  • [ 3 ] [Shen, Hong]Univ Adelaide, Sch Comp Sci, Adelaide, SA, Australia
  • [ 4 ] [Li, Peng]Washington Univ, Dept Comp Sci & Engn, St Louis, MO 14263 USA

Reprint 's Address:

  • 郭龙坤

    [Guo, Longkun]Fuzhou Univ, Sch Math & Comp Sci, Fuzhou, Fujian, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

SPAA'15: PROCEEDINGS OF THE 27TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES

Year: 2015

Page: 62-64

Language: English

Cited Count:

WoS CC Cited Count: 8

SCOPUS Cited Count: 9

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Online/Total:175/10277042
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