Cycle or path polytopes are the convex hulls of the incidence vectors of (directed) cycles or paths in graphs (digraphs), respectively. By admitting not all cardinalities of paths or cycles ($=$ number of edges), we obtain cardinality restricted path or cycle polytopes.

The subject of this project is to investigate the coherence between different cycle and path polytopes. The aim is to gain more insight into these objects and to develop methods for transmission of the associated inequalities. From this we expect to gain advances by the solution of problems in connection with telecommunication and traffic networks such as line planning in public transport.

Publications

2009
Facets of the (s,t)-p-path polytope Discrete Appl. Math., 157(14), pp. 3119-3132, 2009 (preprint available as ) Rüdiger Stephan BibTeX
DOI
Cycle and Path Polytopes with and without Length Restrictions
On the cycle polytope of a directed graph and its relaxations Networks, 54(1), pp. 47-55, 2009 Egon Balas, Rüdiger Stephan BibTeX
DOI
Cycle and Path Polytopes with and without Length Restrictions
2005
Polytopes associated with length restricted directed circuits diploma thesis, Technische Universität Berlin, 2005 Rüdiger Stephan BibTeX
Cycle and Path Polytopes with and without Length Restrictions