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

author:

Guo, Longkun (Guo, Longkun.) [1] | Shen, Hong (Shen, Hong.) [2] | Liao, Kewen (Liao, Kewen.) [3] | Li, Peng (Li, Peng.) [4]

Indexed by:

EI

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:

Approximation algorithms Graph theory Polynomial approximation

Community:

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

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

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:164/10278991
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