Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP (Journal of Computational Mathematics, 2018)
Transformations of Steiner tree problem variants have been frequently discussed in theliterature. Besides allowing to easily transfer complexity results, they constitute a centralpillar of exact state-of-the-art solvers for well-known variants such as the Steiner treeproblem in graphs. In this article transformations for both the prize-collecting Steiner treeproblem and the maximum-weight connected subgraph problem to the Steiner arborescenceproblem are introduced for the first time. Furthermore, the considerable implications forpractical solving approaches will be demonstrated, including the computation of strongupper and lower bounds.
Keywords: Prize-collecting Steiner tree problem; Maximum-weight connected subgraph problem; Graph transformations; Dual-ascent heuristics.