arrow
Volume 36, Issue 3
Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP

Daniel Rehfeldt & Thorsten Koch

J. Comp. Math., 36 (2018), pp. 459-468.

Published online: 2018-06

Export citation
  • Abstract

Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.

  • Keywords

Prize-collecting Steiner tree problem, Maximum-weight connected subgraph problem, Graph transformations, Dual-ascent heuristics.

  • AMS Subject Headings

90C27, 90C35, 90C10, 90C90

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

rehfeldt@zib.de (Daniel Rehfeldt)

koch@zib.de (Thorsten Koch)

  • BibTex
  • RIS
  • TXT
@Article{JCM-36-459, author = {Daniel and Rehfeldt and rehfeldt@zib.de and 6807 and Department of Mathematics, Technische Universität Berlin, Germany and Daniel Rehfeldt and Thorsten and Koch and koch@zib.de and 5423 and Zuse Institute Berlin and Technische Universitat Berlin, Germany and Thorsten Koch}, title = {Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP}, journal = {Journal of Computational Mathematics}, year = {2018}, volume = {36}, number = {3}, pages = {459--468}, abstract = {

Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1709-m2017-0002}, url = {http://global-sci.org/intro/article_detail/jcm/12271.html} }
TY - JOUR T1 - Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP AU - Rehfeldt , Daniel AU - Koch , Thorsten JO - Journal of Computational Mathematics VL - 3 SP - 459 EP - 468 PY - 2018 DA - 2018/06 SN - 36 DO - http://doi.org/10.4208/jcm.1709-m2017-0002 UR - https://global-sci.org/intro/article_detail/jcm/12271.html KW - Prize-collecting Steiner tree problem, Maximum-weight connected subgraph problem, Graph transformations, Dual-ascent heuristics. AB -

Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.

Daniel Rehfeldt & Thorsten Koch. (2020). Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP. Journal of Computational Mathematics. 36 (3). 459-468. doi:10.4208/jcm.1709-m2017-0002
Copy to clipboard
The citation has been copied to your clipboard