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

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-9485(online) ISSN 0273-0979(print)

Authors: Gil Kalai and Daniel J. Kleitman
Journal: Bull. Amer. Math. Soc. 26 (1992), 315-316
MSC (2000): Primary 52B55
MathSciNet review: 1130448
Full-text PDF

Abstract: The diameter of the graph of a d-dimensional polyhedron with n facets is at most ${n^{\log d + 2}}$

[1] David Barnette, 𝑊ᵥ paths on 3-polytopes, J. Combinatorial Theory 7 (1969), 62–70. MR 0248636 (40 #1887)
[2] George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. MR 0201189 (34 #1073)
[3] Branko Grünbaum, Convex polytopes, With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. MR 0226496 (37 #2085)
[4] Gil Kalai, Upper bounds for the diameter and height of graphs of convex polyhedra, Discrete Comput. Geom. 8 (1992), no. 4, 363–372. MR 1176376 (93i:52017), http://dx.doi.org/10.1007/BF02293053
[5] Victor Klee and Peter Kleinschmidt, The 𝑑-step conjecture and its relatives, Math. Oper. Res. 12 (1987), no. 4, 718–755. MR 913867 (89a:52018), http://dx.doi.org/10.1287/moor.12.4.718
[6] Victor Klee and David W. Walkup, The 𝑑-step conjecture for polyhedra of dimension 𝑑<6, Acta Math. 117 (1967), 53–78. MR 0206823 (34 #6639)
[7] D. G. Larman, Paths of polytopes, Proc. London Math. Soc. (3) 20 (1970), 161–178. MR 0254735 (40 #7942)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|