A quasi-polynomial bound for the diameter\\of graphs of polyhedra
From MaRDI portal
Publication:4005821
DOI10.1090/S0273-0979-1992-00285-9zbMath0751.52006arXivmath/9204233OpenAlexW2592711915WikidataQ29012970 ScholiaQ29012970MaRDI QIDQ4005821
Publication date: 27 September 1992
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9204233
Related Items
Diameters of cocircuit graphs of oriented matroids: an update, Improving bounds on the diameter of a polyhedron in high dimensions, On the complexity of computing the diameter of a polytope, On the complexity of some basic problems in computational convexity. I. Containment problems, Lattice-free polytopes and their diameter, More bounds on the diameters of convex polytopes, Obstructions to weak decomposability for simplicial polytopes, Linear programming, the simplex algorithm and simple polytopes, Criss-cross methods: A fresh view on pivot algorithms, Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex-Decomposable, On circuit diameter bounds via circuit imbalances, Distance between vertices of lattice polytopes, Hirsch polytopes with exponentially long combinatorial segments, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Topological Prismatoids and Small Simplicial Spheres of Large Diameter, Monotone diameter of bisubmodular polyhedra, Primitive point packing, The diameter of lattice zonotopes, On the Combinatorial Diameters of Parallel and Series Connections, Polyhedral graph abstractions and an approach to the linear Hirsch conjecture, A counterexample to the Hirsch conjecture, A Friendly Smoothed Analysis of the Simplex Method, A double-pivot simplex algorithm and its upper bounds of the iteration numbers, A note on the diameter of convex polytope, Unique sink orientations of grids, Polytopes and arrangements: diameter and curvature, On sub-determinants and the diameter of polyhedra, The worst-case running time of the random simplex algorithm is exponential in the height, George Dantzig's impact on the theory of computation, Improved bounds on the diameter of lattice polytopes, Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count, Upper bounds for the diameter and height of graphs of convex polyhedra, On the circuit diameter conjecture, Unnamed Item, One-point suspensions and wreath products of polytopes and spheres, Complexity of the gravitational method for linear programming, A refinement of Todd's bound for the diameter of a polyhedron, Primitive zonotopes, On the shadow simplex method for curved polyhedra, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, A continuous \(d\)-step conjecture for polytopes, Book Review: The basic George B. Dantzig, An asymptotically improved upper bound on the diameter of polyhedra, Graphs of transportation polytopes, The width of five-dimensional prismatoids, The Hirsch Conjecture Holds for Normal Flag Complexes
Cites Work
