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

The Steiner Connectivity Problem

Please always quote using this URN: urn:nbn:de:0297-zib-11171
  • The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Ralf BorndörferORCiD, Marika Neumann, Marc PfetschORCiD
Document Type:ZIB-Report
Tag:Connectivity; Generalization; Partition Inequalities; Paths; Steiner Tree
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Date of first Publication:2009/02/24
Series (Serial Number):ZIB-Report (09-07)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.