Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.