Packing Steiner trees: Separation algorithms

Grötschel M, Martin A, Weismantel R (1996)

Publication Language: English

Publication Type: Journal article

Publication year: 1996

Journal

SIAM Journal on Discrete Mathematics Society for Industrial and Applied Mathematics

Book Volume: 9

Pages Range: 233 - 257

Abstract

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.

Authors with CRIS profile

Alexander Martin Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

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

How to cite

APA:

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

MLA:

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

BibTeX: Download