On the cycle polytope of a directed graph and its relaxations

DOI10.1002/net.20304zbMath1207.05066OpenAlexW4230235511MaRDI QIDQ3057102

Rüdiger Stephan, Egon Balas

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20304

zbMATH Keywords

permutationscycle polytopetransitive tournaments

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Cycle selections ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Cycle algebras and polytopes of matroids ⋮ The feasible region for consecutive patterns of permutations is a cycle polytope ⋮ An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs

Cites Work

• Unnamed Item
• On removing a vertex from the assignment polytope
• On the dimension of projected polyhedra
• On the monotonization of polyhedra
• \((0,{1\over 2},1)\) matrices which are extreme points of the generalized transitive tournament polytope
• On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope
• Results and problems in the theory of doubly-stochastic matrices
• The Circuit Polytope: Facets
• Blocking and anti-blocking pairs of polyhedra
• Facets of the \(p\)-cycle polytope

This page was built for publication: On the cycle polytope of a directed graph and its relaxations