• search hit 472 of 1103
Back to Result List

The Steiner Connectivity Problem

Please always quote using this URN:urn:nbn:de:0296-matheon-6476
  • 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 important 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 certain 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
Metadaten
Author:Ralf Borndörfer, Marika Neumann, Marc E. Pfetsch
URN:urn:nbn:de:0296-matheon-6476
Referee:Martin Grötschel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2009/03/08
Release Date:2009/07/31
Tag:
Institute:Technische Universität Berlin
Zuse Institute Berlin (ZIB)
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Preprint Number:656
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.