Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
Please always quote using this URN: urn:nbn:de:0297-zib-59777
- 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 paper 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, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.
Download full text files
Additional Services
| Author: | Daniel RehfeldtORCiD, Thorsten KochORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Steiner tree problems; graph transformation; maximum-weight connected subgraph problem; prize-collecting Steiner tree problem |
| MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) |
| Date of first Publication: | 2016/01/07 |
| Series (Serial Number): | ZIB-Report (16-36) |
| ISSN: | 1438-0064 |
| Published in: | Appeared in: Journal of Computational Mathematics, 36(3):459-468, 2018 |
| DOI: | https://doi.org/10.4208/jcm.1709-m2017-0002 |
