A quasi-polynomial bound for the diameter of graphs of polyhedra

1992/01/01 by Gil Kalai, Daniel J. Kleitman · 152 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Polyhedron #Combinatorics #Mathematics #Graph

paper · pdf · doi:10.1090/s0273-0979-1992-00285-9

published in Bulletin of the American Mathematical Society 26(2), 315-316 (American Mathematical Society)

openalex publication_date 1992/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The diameter of the graph of a <italic>d</italic> -dimensional polyhedron with <italic>n</italic> facets is at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n Superscript log d plus 2"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">n^{log d + 2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>

Citations

• The d-step conjecture for polyhedra of dimension d&lt;6

Cited by

• The many facets of linear programming
• Criss-cross methods: A fresh view on pivot algorithms
• Hirsch conjecture [wikipedia]
• Polyhedral combinatorics [wikipedia]