A quasi-polynomial bound for the diameter of graphs of polyhedra
HTML articles powered by AMS MathViewer
- by Gil Kalai and Daniel J. Kleitman PDF
- Bull. Amer. Math. Soc. 26 (1992), 315-316 Request permission
Abstract:
The diameter of the graph of a d-dimensional polyhedron with n facets is at most ${n^{\log d + 2}}$References
- David Barnette, $W_{v}$ paths on 3-polytopes, J. Combinatorial Theory 7 (1969), 62–70. MR 248636
- George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. MR 0201189
- Branko Grünbaum, Convex polytopes, Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. MR 0226496
- 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, DOI 10.1007/BF02293053
- Victor Klee and Peter Kleinschmidt, The $d$-step conjecture and its relatives, Math. Oper. Res. 12 (1987), no. 4, 718–755. MR 913867, DOI 10.1287/moor.12.4.718
- Victor Klee and David W. Walkup, The $d$-step conjecture for polyhedra of dimension $d<6$, Acta Math. 117 (1967), 53–78. MR 206823, DOI 10.1007/BF02395040
- D. G. Larman, Paths of polytopes, Proc. London Math. Soc. (3) 20 (1970), 161–178. MR 254735, DOI 10.1112/plms/s3-20.1.161
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 26 (1992), 315-316
- MSC (2000): Primary 52B55
- DOI: https://doi.org/10.1090/S0273-0979-1992-00285-9
- MathSciNet review: 1130448