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

author:

Guo, Longkun (Guo, Longkun.) [1] (Scholars:郭龙坤) | Zou, Nianchen (Zou, Nianchen.) [2] | Li, Yidong (Li, Yidong.) [3]

Indexed by:

CPCI-S EI Scopus

Abstract:

Let G = (V, E) be a given graph, S subset of V be a terminal set, r is an element of S be the selected root. Assume that c : E -> R+ and d : E -> R+ are cost and delay functions on the edges respectively. The shallow-light Steiner tree (SLST) problem is to compute a minimum cost tree spanning all the terminals of 5, such that the delay between r and every other terminal is bounded by a given delay constraint D is an element of R-0(+). Since in real network, the cost and delay of a link are always related, this paper addresses two such special cases: the constrained Steiner tree (CST) problem, a special case of the SLST problem that c(e) = sigma d(e) for every edge, and the constrained spanning tree (CPT) problem, a further special case of the CST problem when S = V. This paper first shows that even when c(e) = d(c), the CPT problem is NP-hard, and admits no (1 + epsilon, gamma ln (vertical bar V vertical bar) approximation algorithm algorithm for some fixed gamma > 0 and any epsilon < 1/vertical bar V vertical bar+vertical bar E vertical bar+1 The inapproximability result can be applied to the CST problem immediately. Based on the above observation of the hardness to develop a single factor approximation algorithm, we give an approximation algorithm with a bifactor ratio of (rho, 1.39 + 2.78/rho - 1) for the CST problem, where 1.39 is the best approximation ratio for the minimum Steiner tree problem in the current state of the art. As a consequence, for the applications where cost and delay are of equal importance, an approximation with bifactor (2.87, 2.87) for CST can be immediately obtained by setting rho = 1.39 + 2.78/rho - 1. This indicates that the SLST problem admits approximation algorithms with constant bifactor ratio, when the cost and delay are linearly dependent.

Keyword:

Bifactor approximation algorithm constrained spanning tree constrained Steiner tree inapproximability NP-hardness

Community:

  • [ 1 ] [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Peoples R China
  • [ 2 ] [Zou, Nianchen]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Peoples R China
  • [ 3 ] [Li, Yidong]Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing, Peoples R China

Reprint 's Address:

  • 郭龙坤

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

Email:

Show more details

Related Keywords:

Source :

2014 SIXTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND PROGRAMMING (PAAP)

ISSN: 2168-3034

Year: 2014

Page: 99-103

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:139/10279872
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