Indexed by:
Abstract:
In this paper, we consider the k-prize-collecting Steiner tree problem (k-PCST), extending both the prize-collecting Steiner tree problem (PCST) and the k-minimum spanning tree problem (k-MST). In this problem, we are given a connected graph G=(V,E), a root vertex r and an integer k. Every edge in E has a nonnegative cost. Every vertex in V has a nonnegative penalty cost. We want to find an r-rooted tree F that spans at least k vertices such that the total cost, including the edge cost of the tree F and the penalty cost of the vertices not spanned by F, is minimized. Our main contribution is to present a 5-approximation algorithm for the k-PCST via the methods of primal-dual and Lagrangean relaxation.
Keyword:
Reprint Author's Address:
Source :
OPTIMIZATION LETTERS
ISSN: 1862-4472
Year: 2019
Issue: 3
Volume: 13
Page: 573-585
1 . 6 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:54
JCR Journal Grade:2
Cited Count:
WoS CC Cited Count: 10
SCOPUS Cited Count: 13
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 9
Affiliated Colleges: