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 |

