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

author:

Shen, Hong (Shen, Hong.) [1] | Guo, Longkun (Guo, Longkun.) [2] (Scholars:郭龙坤)

Indexed by:

EI Scopus SCIE

Abstract:

For a given undirected (edge) weighted graph G = (V, E), a terminal set S subset of V and a root r is an element of S, the rooted k-vertex connected minimum Steiner network (kVSMN(r)) problem requires to construct a minimum-cost subgraph of G such that each terminal in S \ {r} is k-vertex connected to r. As an important problem in survivable network design, the kVSMNr problem is known to be NP-hard even when k = 1 [14]. For k = 3 this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov [20]. Our algorithm constructs an approximate 3VSMNr through augmenting a two-vertex connected counterpart with additional edges of bounded cost to the optimal. We prove that the total cost of the added edges is at most six times of the optimal by showing that the edges in a 3VSMNr compose a subgraph containing our solution in such a way that each edge appears in the subgraph at most six times.

Keyword:

approximation algorithm Rooted three-vertex connectivity Steiner minimum network survivable network design

Community:

  • [ 1 ] [Shen, Hong]Sun Yat Sen Univ, Sch Informat Sci & Technol, Guangzhou, Guangdong, Peoples R China
  • [ 2 ] [Shen, Hong]Univ Adelaide, Sch Comp Sci, Adelaide, SA 5005, Australia
  • [ 3 ] [Guo, Longkun]Fuzhou Univ, Sch Math & Comp Sci, Fuzhou 350108, Fujian, Peoples R China

Reprint 's Address:

  • [Shen, Hong]Sun Yat Sen Univ, Sch Informat Sci & Technol, Guangzhou, Guangdong, Peoples R China

Show more details

Related Keywords:

Source :

IEEE TRANSACTIONS ON COMPUTERS

ISSN: 0018-9340

Year: 2013

Issue: 9

Volume: 62

Page: 1684-1693

1 . 4 7 3

JCR@2013

3 . 6 0 0

JCR@2023

ESI Discipline: COMPUTER SCIENCE;

JCR Journal Grade:2

CAS Journal Grade:3

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:133/10050775
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