Zurück zu den Preprints des Jahres 2003


Regular Delta-path inequalities for the k-cycle polytope

by E.Girlich, M.Höding, A.Horbach.

Series: 2003-15, Preprints

90C27 Combinatorial optimization

We investigate the facet structure of the symmetric k-cycle
polytope which is the convex hull of the incident vectors
of all the k-cycles in the complete undirected graph.
We suggest a new class of facet inequalities for the k-cycle
polytope which is a generalization of the regular path
inequalities introduced by Denis Naddef and Giovanni
Rinaldi for the travelling salesman polytope.

k-cycle polytope, travelling salesman polytope, path inequalities