Bulletin of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

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

Author(s): Gil Kalai; Daniel J. Kleitman
Journal: Bull. Amer. Math. Soc. 26 (1992), 315-316.
MSC (2000): Primary 52B55
MathSciNet review: 1130448
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

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

References:

[1]: D. W. Barnette, ${W_v}$ paths on 3-polytopes, J. Combin. Theory 7 (1969), 62-70. MR 0248636 (40:1887)
[2]: G. B. Dantzig, Linear programming and extensions, Princeton Univ. Press, Princeton, NJ 1963. MR 0201189 (34:1073)
[3]: B. Grübaum, Convex polytopes, Wiley Interscience, London, 1967. MR 0226496 (37:2085)
[4]: G. Kalai, Upper bounds for the diameter and height of polytopes, Discrete Comput. Geom. 7(1992) (to appear). MR 1176376 (93i:52017)
[5]: V. Klee and P. Kleinschmidt, The d-steps conjecture and its relatives, Math. Operation Research 12 (1987), 718-755. MR 913867 (89a:52018)
[6]: V. Klee and D. Walkup, The d-step conjecture for polyhedra of dimension , Acta Math. 133(1967), 53-78. MR 0206823 (34:6639)
[7]: D. G. Larman, Paths on 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
\|