Packing Steiner trees: Separation algorithms

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autorinnen und Autoren: Grötschel M, Martin A, Weismantel R
Zeitschrift: SIAM Journal on Discrete Mathematics
Jahr der Veröffentlichung: 1996
Band: 9
Seitenbereich: 233 - 257
ISSN: 0895-4801
Sprache: Englisch


We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


Grötschel, M., Martin, A., & Weismantel, R. (1996). Packing Steiner trees: Separation algorithms. SIAM Journal on Discrete Mathematics, 9, 233 - 257.

Grötschel, Martin, Alexander Martin, and Robert Weismantel. "Packing Steiner trees: Separation algorithms." SIAM Journal on Discrete Mathematics 9 (1996): 233 - 257.


Zuletzt aktualisiert 2018-08-08 um 03:51