Optimum path packing on wheels: The consecutive case

Journal article

Publication Details

Author(s): Grötschel M, Martin A, Weismantel R
Journal: Computers & Mathematics With Applications
Publication year: 1996
Volume: 31
Pages range: 23 - 35
ISSN: 0898-1221
Language: English


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 Authors / FAU Editors

Martin, Alexander Prof. Dr.
Economics - Discrete Optimization - Mathematics (EDOM)

External institutions with authors

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

How to cite

Grötschel, M., Martin, A., & Weismantel, R. (1996). Optimum path packing on wheels: The consecutive case. Computers & Mathematics With Applications, 31, 23 - 35.

Grötschel, Martin, Alexander Martin, and Robert Weismantel. "Optimum path packing on wheels: The consecutive case." Computers & Mathematics With Applications 31 (1996): 23 - 35.


Last updated on 2018-07-08 at 16:08