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

On cardinality constrained cycle and path polytopes

Please always quote using this URN: urn:nbn:de:0297-zib-10093
  • We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Volker Kaibel, Rüdiger Stephan
Document Type:ZIB-Report
Tag:cycles; facets; integer characterizations; path
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C38 Paths and cycles [See also 90B10]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Date of first Publication:2007/10/02
Series (Serial Number):ZIB-Report (07-25)
ISSN:1438-0064
ZIB-Reportnumber:07-25
Published in:Appeared in: On cardinality constrained cycle and path polytopes Math. Program. (Ser. A) 123 (2), 2010, 371-394
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.