Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 64 of 210
Back to Result List

Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem

Please always quote using this URN: urn:nbn:de:0297-zib-60420
  • 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 paper 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 percent 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.
Metadaten
Author:Daniel RehfeldtORCiD, Thorsten KochORCiD, Stephen J. Maher
Document Type:ZIB-Report
Tag:Steiner tree problems; maximum-weight connected subgraph problem; prize-collecting Steiner tree problem; reduction techniques
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:D. Software
Date of first Publication:2016/09/23
Series (Serial Number):ZIB-Report (16-47)
ISSN:1438-0064
DOI:https://doi.org/10.1002/net.21857
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.