{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T21:10:43Z","timestamp":1771535443710,"version":"3.50.1"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1007\/bf01206636","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T15:18:10Z","timestamp":1109258290000},"page":"207-219","source":"Crossref","is-referenced-by-count":11,"title":["On the complexity of computing the diameter of a polytope"],"prefix":"10.1007","volume":"4","author":[{"given":"Alan M.","family":"Frieze","sequence":"first","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey andD. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computation","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems. InComplexity of Computer Computation ed.R. E. Miller andThatcher, Plenum, New York, 1972, 85?103."},{"key":"CR3","unstructured":"G. Kalai,Subexponential Bound for the d-step Problem. Manuscript, IBM Almaden Research Center, 1991."},{"issue":"2","key":"CR4","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G. Kalai","year":"1992","unstructured":"G. Kalai andD. J. Kleitman. A quasi-polynomial bound for diameter of graphs of polyhedra.Bull. Amer. Math. Soc. 26 (2) (April 1992), 315?316.","journal-title":"Bull. Amer. Math. Soc."},{"issue":"2","key":"CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02392139","volume":"133","author":"V. Klee","year":"1974","unstructured":"V. Klee, Polytope pairs and their relationship to linear programming.Acta Mathematica 133 (2) (October 1974), 1?25.","journal-title":"Acta Mathematica"},{"key":"CR6","first-page":"415","volume":"4","author":"B. Korte","year":"1981","unstructured":"B. Korte andR. Schrader, On the existence of fast approximating scheme.Nonlinear Programming 4 (1981), 415?437.","journal-title":"Nonlinear Programming"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1112\/plms\/s3-20.1.161","volume":"30","author":"D. G. Larman","year":"1970","unstructured":"D. G. Larman, Path on polytopes.Proc. Lond. Math. Soc. 30 (1970), 161?178.","journal-title":"Proc. Lond. Math. Soc."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. H. Papadimitriou","year":"1984","unstructured":"C. H. Papadimitriou andM. Yannakakis, The complexity of facets.J. Comput. System Sci. 28, (1984), 244?259.","journal-title":"J. Comput. System Sci."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer, The polynomial-time hierarchy.Theoret. Comput. Sci. 3 (1977), 1?22.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206636.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01206636\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206636","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T17:10:17Z","timestamp":1556730617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01206636"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF01206636"],"URL":"https:\/\/doi.org\/10.1007\/bf01206636","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}