Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP

  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Daniel RehfeldtORCiD, Thorsten KochORCiD
Document Type:Article
Parent Title (English):Journal of Computational Mathematics
Volume:36
Issue:3
First Page:459
Last Page:468
Date of first Publication:2018/03/28
Preprint:urn:nbn:de:0297-zib-59777
DOI:https://doi.org/10.4208/jcm.1709-m2017-0002
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.