Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/80009
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorShen, H.en
dc.contributor.authorGuo, L.en
dc.date.issued2013en
dc.identifier.citationIEEE Transactions on Computers, 2013; 62(9):1684-1693en
dc.identifier.issn0018-9340en
dc.identifier.issn1557-9956en
dc.identifier.urihttp://hdl.handle.net/2440/80009-
dc.description.abstractFor a given undirected (edge) weighted graph G = (V, E), a terminal set S ⊆ V and a root r ∈ S, the rooted k-vertex connected minimum Steiner network (kVSMNr) problem requires to construct a minimum-cost subgraph of G such that each terminal in S {R} is k-vertex connected to τ. As an important problem in survivable network design, the kVSMNτ problem is known to be NP-hard even when k 1/4 1 [14]. For k 1/4 3 this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov [20]. Our algorithm constructs an approximate 3VSMNτ 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 3VSMNτ compose a subgraph containing our solution in such a way that each edge appears in the subgraph at most six times.en
dc.description.statementofresponsibilityHong Shen, Longkun Guoen
dc.language.isoenen
dc.publisherIEEE Computer Socen
dc.rightsCopyright status unknownen
dc.titleAn eight-approximation algorithm for computing rooted three-vertex connected minimum steiner networksen
dc.typeJournal articleen
dc.identifier.rmid0020130890en
dc.identifier.doi10.1109/TC.2012.170en
dc.identifier.pubid18582-
pubs.library.collectionComputer Science publicationsen
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
dc.identifier.orcidShen, H. [0000-0002-3663-6591]en
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_80009.pdfRestricted Access383.13 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.