Rights statement: This is the peer reviewed version of the following article: Rehfeldt D, Koch T, Maher SJ. Reduction techniques for the prize collecting Steiner tree problem and the maximum‐weight connected subgraph problem. Networks. 2018;1–28. https://doi.org/10.1002/net.21857 which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/net.21857 This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
Accepted author manuscript, 566 KB, PDF document
Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Reduction techniques for the prize collecting Steiner tree problem and the maximum‐weight connected subgraph problem
AU - Rehfeldt, Daniel
AU - Koch, Thorsten
AU - Maher, Stephen
N1 - This is the peer reviewed version of the following article: Rehfeldt D, Koch T, Maher SJ. Reduction techniques for the prize collecting Steiner tree problem and the maximum‐weight connected subgraph problem. Networks. 2018;1–28. https://doi.org/10.1002/net.21857 which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/net.21857 This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
PY - 2019/3
Y1 - 2019/3
N2 - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this article we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize‐collecting Steiner tree problem, the rooted prize‐collecting Steiner tree problem and the maximum‐weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90% of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state‐of‐the‐art Steiner problem solver SCIP‐Jack.
AB - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this article we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize‐collecting Steiner tree problem, the rooted prize‐collecting Steiner tree problem and the maximum‐weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90% of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state‐of‐the‐art Steiner problem solver SCIP‐Jack.
KW - maximum‐weight connected subgraph problem
KW - prize‐collecting Steiner tree problem
KW - reduction techniques
KW - rooted prize‐collecting Steiner tree problem
KW - Steiner tree problem
KW - Steiner tree reductions
U2 - 10.1002/net.21857
DO - 10.1002/net.21857
M3 - Journal article
VL - 73
SP - 206
EP - 233
JO - Networks
JF - Networks
SN - 0028-3045
IS - 2
ER -