Optimum Path Packing on Wheels: The Consecutive Case
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-1976
- 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.
Verfasserangaben: | Martin Grötschel, Alexander Martin, Robert Weismantel |
---|---|
Dokumentart: | ZIB-Report |
Datum der Erstveröffentlichung: | 29.11.1995 |
Schriftenreihe (Bandnummer): | ZIB-Report (SC-95-31) |
ZIB-Reportnummer: | SC-95-31 |
Verlagspublikation: | Appeared in: Computers Math. Applic., Vol. 31, No. 11, pp. 23-35, 1996 |