Zurück zu den Preprints des Jahres 2003


2003-15

Regular Delta-path inequalities for the k-cycle polytope

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


Series: 2003-15, Preprints

MSC:
90C27 Combinatorial optimization

Abstract:
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.

Keywords:
k-cycle polytope, travelling salesman polytope, path inequalities