On the circuit diameter conjecture

DOI10.1007/s00454-018-9995-yzbMath1401.52019arXiv1611.08039OpenAlexW2962693383WikidataQ123009327 ScholiaQ123009327MaRDI QIDQ1991340

Tamon Stephen, Steffen Borgwardt, Timothy Yusun

Publication date: 30 October 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.08039

zbMATH Keywords

polyhedradiametercircuitHirsch conjecture

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Linear programming (90C05) Distance in graphs (05C12)

Related Items

On circuit diameter bounds via circuit imbalances, Circuit walks in integral polyhedra, Constructing Clustering Transformations, On the Circuit Diameter of Some Combinatorial Polytopes, A polyhedral model for enumeration and optimization over the set of circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The circuit diameter of the Klee-Walkup polyhedron
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids
• A counterexample to the Hirsch conjecture
• An update on the Hirsch conjecture
• The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes
• Many polytopes meeting the conjectured Hirsch bound
• More polytopes meeting the conjectured Hirsch bound
• Counterexamples to the strong \(d\)-step conjecture for \(d\geq 5\)
• Hirsch polytopes with exponentially long combinatorial segments
• Edges versus circuits: a hierarchy of diameters in polyhedra
• The hierarchy of circuit diameters and transportation polytopes
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• The Hirsch conjecture is true for (0,1)-polytopes
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Diameter of Polyhedra: Limits of Abstraction
• On the Circuit Diameter of Dual Transportation Polyhedra
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• The d-Step Conjecture and Its Relatives
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets
• The width of five-dimensional prismatoids
• Computing Maximal Copies of Polyhedra Contained in a Polyhedron
• More bounds on the diameters of convex polytopes
• An enumeration of simplicial 4-polytopes with 8 vertices