Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
Please always quote using this URN: urn:nbn:de:0297-zib-65439
- This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches.
Author: | Daniel RehfeldtORCiD, Thorsten KochORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | Steiner tree; maximum-weight connected subgraph |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
Date of first Publication: | 2017/10/27 |
Series (Serial Number): | ZIB-Report (17-57) |
ISSN: | 1438-0064 |