Optimum Path Packing on Wheels: The Noncrossing Case.
Please always quote using this URN: urn:nbn:de:0297-zib-1225
- We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that no two terminal pairs cross, 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.
Download full text files
Additional Services
| Author: | Martin Grötschel, Alexander Martin, Robert Weismantel |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1993/10/27 |
| Series (Serial Number): | ZIB-Report (SC-93-26) |
| ZIB-Reportnumber: | SC-93-26 |
| Published in: | See SC 95-31 for an updated version |
