Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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 Statistics - number of accesses to the document
Author:Daniel RehfeldtORCiD, Thorsten KochORCiD
Document Type:ZIB-Report
Tag:Steiner tree; maximum-weight connected subgraph
Date of first Publication:2017/10/27
Series (Serial Number):ZIB-Report (17-57)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.