Premium
On the cycle polytope of a directed graph
Author(s) -
Balas Egon,
Oosten Maarten
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200008)36:1<34::aid-net4>3.0.co;2-2
Subject(s) - polytope , combinatorics , convex hull , birkhoff polytope , uniform k 21 polytope , convex polytope , polyhedral combinatorics , mathematics , directed graph , travelling salesman problem , computer science , discrete mathematics , regular polygon , convex set , algorithm , convex optimization , geometry
We give a partial description of the cycle polytope of a directed graph G , that is, the convex hull of the incidence vectors of simple directed cycles of G . First, we show how to obtain facets of the cycle polytope from facets of the asymmetric traveling salesman polytope. This involves lifting and facet projection. We discuss several lifting procedures. Next, we obtain facets that have a different source. In particular, we give a complete characterization of the facets that cut off the origin. No such characterization is known for the cycle polytope of an undirected graph. Finally, we introduce a useful equivalence class among the inequalities defining the cycle polytope. © 2000 John Wiley & Sons, Inc.