Upper bounds for the diameter and height of graphs of convex polyhedra

DOI10.1007/BF02293053zbMath0764.52003WikidataQ56503922 ScholiaQ56503922MaRDI QIDQ1196197

Gil Kalai

Publication date: 17 December 1992

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

Full work available at URL: https://eudml.org/doc/131225

zbMATH Keywords

diameterHirsch conjecturequasi-polynomial bound

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Related Items (14)

Linear programming, the simplex algorithm and simple polytopes ⋮ A quasi-polynomial bound for the diameter\\of graphs of polyhedra ⋮ Hirsch polytopes with exponentially long combinatorial segments ⋮ Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Monotone diameter of bisubmodular polyhedra ⋮ Polyhedral graph abstractions and an approach to the linear Hirsch conjecture ⋮ Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count ⋮ On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes ⋮ Unnamed Item ⋮ One-point suspensions and wreath products of polytopes and spheres ⋮ Monotone paths in geometric triangulations ⋮ Computing in combinatorial optimization ⋮ The Hirsch Conjecture Holds for Normal Flag Complexes ⋮ On the Length of Monotone Paths in Polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The d-Step Conjecture and Its Relatives
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Wv paths on 3-polytopes
• Paths on Polytopes
• The maximum numbers of faces of a convex polytope

This page was built for publication: Upper bounds for the diameter and height of graphs of convex polyhedra