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

Author:

Han, Lu (Han, Lu.) | Wang, Changjun (Wang, Changjun.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

EI Scopus

Abstract:

In this paper, we study the prize-collecting k-Steiner tree problem (PC k-ST), which is an interesting generalization of both the k-Steiner tree problem (k-ST) and the prize-collecting Steiner tree problem (PCST). In the PC k-ST, we are given an undirected connected graph G= (V, E), a subset R⊆ V called terminals, a root vertex r∈ V and an integer k. Every edge has a non-negative edge cost and every vertex has a non-negative penalty cost. We wish to find an r-rooted tree F that spans at least k vertices in R so as to minimize the total edge costs of F as well as the penalty costs of the vertices not in F. As our main contribution, we propose two approximation algorithms for the PC k-ST with ratios of 5.9672 and 5. The first algorithm is based on an observation of the solutions for the k-ST and the PCST, and the second one is based on the technique of primal-dual. © 2021, Springer Nature Switzerland AG.

Keyword:

Trees (mathematics) Approximation algorithms

Author Community:

  • [ 1 ] [Han, Lu]Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing; 100190, China
  • [ 2 ] [Wang, Changjun]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Xu, Dachuan]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 4 ] [Zhang, Dongmei]School of Computer Science and Technology, Shandong Jianzhu University, Jinan; 250101, China

Reprint Author's Address:

  • [zhang, dongmei]school of computer science and technology, shandong jianzhu university, jinan; 250101, china

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2021

Volume: 12606 LNCS

Page: 371-378

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: 12

Affiliated Colleges:

Online/Total:376/10642578
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.