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