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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Daniel Rehfeldt, Thorsten Koch
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