6543
eng
reportzib
0
--
2017-10-27
--
Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
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.
1438-0064
urn:nbn:de:0297-zib-65439
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
17-57
eng
uncontrolled
Steiner tree
eng
uncontrolled
maximum-weight connected subgraph
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6543/note.pdf