{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T21:10:45Z","timestamp":1771535445127,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T00:00:00Z","timestamp":1524528000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s00454-018-9995-y","type":"journal-article","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T13:37:41Z","timestamp":1524577061000},"page":"558-587","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["On the Circuit Diameter Conjecture"],"prefix":"10.1007","volume":"60","author":[{"given":"Steffen","family":"Borgwardt","sequence":"first","affiliation":[]},{"given":"Tamon","family":"Stephen","sequence":"additional","affiliation":[]},{"given":"Timothy","family":"Yusun","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,24]]},"reference":[{"issue":"2","key":"9995_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0012-365X(80)90029-1","volume":"31","author":"A Altshuler","year":"1980","unstructured":"Altshuler, A., Bokowski, J., Steinberg, L.: The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes. Discrete Math. 31(2), 115\u2013124 (1980)","journal-title":"Discrete Math."},{"issue":"4","key":"9995_CR2","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1515\/advgeom-2016-0020","volume":"16","author":"S Borgwardt","year":"2016","unstructured":"Borgwardt, S., De Loera, J.A., Finhold, E.: Edges versus circuits: a hierarchy of diameters in polyhedra. Adv. Geom. 16(4), 511\u2013530 (2016)","journal-title":"Adv. Geom."},{"key":"9995_CR3","doi-asserted-by":"publisher","unstructured":"Borgwardt, S., De Loera, J.A., Finhold, E.: The diameters of network-flow polytopes satisfy the Hirsch conjecture. Math. Program. (2017). \n                    https:\/\/doi.org\/10.1007\/s10107-017-1176-x","DOI":"10.1007\/s10107-017-1176-x"},{"key":"9995_CR4","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.dam.2015.10.017","volume":"240","author":"S Borgwardt","year":"2018","unstructured":"Borgwardt, S., De Loera, J.A., Finhold, E., Miller, J.: The hierarchy of circuit diameters and transportation polytopes. Discrete Appl. Math. 240, 8\u201324 (2018)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9995_CR5","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1137\/140976868","volume":"29","author":"S Borgwardt","year":"2015","unstructured":"Borgwardt, S., Finhold, E., Hemmecke, R.: On the circuit diameter of dual transportation polyhedra. SIAM J. Discrete Math. 29(1), 113\u2013121 (2015)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9995_CR6","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1080\/10586458.2011.564965","volume":"20","author":"D Bremner","year":"2011","unstructured":"Bremner, D., Schewe, L.: Edge-graph diameter bounds for convex polytopes with few facets. Exp. Math. 20(3), 229\u2013237 (2011)","journal-title":"Exp. Math."},{"issue":"3","key":"9995_CR7","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1080\/10556788.2012.668906","volume":"28","author":"D Bremner","year":"2013","unstructured":"Bremner, D., Deza, A., Hua, W., Schewe, L.: More bounds on the diameters of convex polytopes. Optim. Methods Softw. 28(3), 442\u2013450 (2013)","journal-title":"Optim. Methods Softw."},{"key":"9995_CR8","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179","volume-title":"Linear Programming and Extensions","author":"GB Dantzig","year":"1963","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)"},{"issue":"4","key":"9995_CR9","doi-asserted-by":"publisher","first-page":"2494","DOI":"10.1137\/151002915","volume":"25","author":"JA Loera De","year":"2015","unstructured":"De Loera, J.A., Hemmecke, R., Lee, J.: On augmentation algorithms for linear and integer-linear programming: from Edmonds-Karp to Bland and beyond. SIAM J. Optim. 25(4), 2494\u20132511 (2015)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"9995_CR10","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1287\/moor.1100.0470","volume":"35","author":"F Eisenbrand","year":"2010","unstructured":"Eisenbrand, F., H\u00e4hnle, N., Razborov, A., Rothvo\u00df, T.: Diameter of polyhedra: limits of abstraction. Math. Oper. Res. 35(4), 786\u2013794 (2010)","journal-title":"Math. Oper. Res."},{"key":"9995_CR11","unstructured":"Firsching, M.: Optimization Methods in Discrete Geometry. Ph.D.\u00a0thesis, Freie Universit\u00e4t of Berlin, Berlin (2015). \n                    http:\/\/d-nb.info\/1083985884\/34"},{"issue":"1\u20133","key":"9995_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0012-365X(99)00017-5","volume":"205","author":"K Fritzsche","year":"1999","unstructured":"Fritzsche, K., Holt, F.B.: More polytopes meeting the conjectured Hirsch bound. Discrete Math. 205(1\u20133), 77\u201384 (1999)","journal-title":"Discrete Math."},{"key":"9995_CR13","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/S0021-9800(67)80055-3","volume":"2","author":"B Gr\u00fcnbaum","year":"1967","unstructured":"Gr\u00fcnbaum, B., Sreedharan, V.P.: An enumeration of simplicial \n                    \n                      \n                    \n                    $$4$$\n                    \n                      \n                        \n                          4\n                        \n                      \n                    \n                  -polytopes with \n                    \n                      \n                    \n                    $$8$$\n                    \n                      \n                        \n                          8\n                        \n                      \n                    \n                   vertices. J. Comb. Theory 2, 437\u2013465 (1967)","journal-title":"J. Comb. Theory"},{"issue":"1","key":"9995_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/PL00009334","volume":"19","author":"F Holt","year":"1998","unstructured":"Holt, F., Klee, V.: Counterexamples to the strong \n                    \n                      \n                    \n                    $$d$$\n                    \n                      \n                        d\n                      \n                    \n                  -step conjecture for \n                    \n                      \n                    \n                    $$d\\ge 5$$\n                    \n                      \n                        \n                          d\n                          \u2265\n                          5\n                        \n                      \n                    \n                  . Discrete Comput. Geom. 19(1), 33\u201346 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9995_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009372","volume":"20","author":"FB Holt","year":"1998","unstructured":"Holt, F.B., Klee, V.: Many polytopes meeting the conjectured Hirsch bound. Discrete Comput. Geom. 20(1), 1\u201317 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9995_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G Kalai","year":"1992","unstructured":"Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Am. Math. Soc. 26(2), 315\u2013316 (1992)","journal-title":"Bull. Am. Math. Soc."},{"issue":"2","key":"9995_CR17","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1365\/s13291-010-0001-8","volume":"112","author":"ED Kim","year":"2010","unstructured":"Kim, E.D., Santos, F.: An update on the Hirsch conjecture. Jahresber. Dtsch. Math.-Ver. 112(2), 73\u201398 (2010)","journal-title":"Jahresber. Dtsch. Math.-Ver."},{"issue":"4","key":"9995_CR18","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1287\/moor.12.4.718","volume":"12","author":"V Klee","year":"1987","unstructured":"Klee, V., Kleinschmidt, P.: The \n                    \n                      \n                    \n                    $$d$$\n                    \n                      \n                        d\n                      \n                    \n                  -step conjecture and its relatives. Math. Oper. Res. 12(4), 718\u2013755 (1987)","journal-title":"Math. Oper. Res."},{"key":"9995_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF02395040","volume":"117","author":"V Klee","year":"1967","unstructured":"Klee, V., Walkup, D.W.: The \n                    \n                      \n                    \n                    $$d$$\n                    \n                      \n                        d\n                      \n                    \n                  -step conjecture for polyhedra of dimension \n                    \n                      \n                    \n                    $$d < 6$$\n                    \n                      \n                        \n                          d\n                          <\n                          6\n                        \n                      \n                    \n                  . Acta Math. 117, 53\u201378 (1967)","journal-title":"Acta Math."},{"issue":"2","key":"9995_CR20","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/s10107-016-1099-y","volume":"165","author":"J-P Labb\u00e9","year":"2017","unstructured":"Labb\u00e9, J.-P., Manneville, T., Santos, F.: Hirsch polytopes with exponentially long combinatorial segments. Math. Program. 165(2), 663\u2013688 (2017)","journal-title":"Math. Program."},{"issue":"3","key":"9995_CR21","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1112\/plms\/pdu064","volume":"110","author":"B Matschke","year":"2015","unstructured":"Matschke, B., Santos, F., Weibel, C.: The width of five-dimensional prismatoids. Proc. Lond. Math. Soc. 110(3), 647\u2013672 (2015)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"1","key":"9995_CR22","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01589099","volume":"45","author":"D Naddef","year":"1989","unstructured":"Naddef, D.: The Hirsch conjecture is true for \n                    \n                      \n                    \n                    $$(0,1)$$\n                    \n                      \n                        \n                          (\n                          0\n                          ,\n                          1\n                          )\n                        \n                      \n                    \n                  -polytopes. Math. Program. 45(1), 109\u2013110 (1989)","journal-title":"Math. Program."},{"key":"9995_CR23","series-title":"The University of North Carolina Monograph Series in Probability and Statistics","first-page":"104","volume-title":"Combinatorial Mathematics and Its Applications","author":"RT Rockafellar","year":"1969","unstructured":"Rockafellar, R.T.: The elementary vectors of a subspace of \n                    \n                      \n                    \n                    $$R^{N}$$\n                    \n                      \n                        \n                          R\n                          N\n                        \n                      \n                    \n                  . In: Bose, R.C., Dowling, T.A. (eds.) Combinatorial Mathematics and Its Applications. The University of North Carolina Monograph Series in Probability and Statistics, vol. 4, pp. 104\u2013127. University of North Carolina Press, Chapel Hill (1969)"},{"issue":"1","key":"9995_CR24","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2012","unstructured":"Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383\u2013412 (2012)","journal-title":"Ann. Math."},{"issue":"3","key":"9995_CR25","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00454-011-9361-9","volume":"47","author":"F Santos","year":"2012","unstructured":"Santos, F., Stephen, T., Thomas, H.: Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids. Discrete Comput. Geom. 47(3), 569\u2013576 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9995_CR26","doi-asserted-by":"crossref","unstructured":"Stephen, T., Yusun, T.: The circuit diameter of the Klee\u2013Walkup polyhedron. In: Proceedings of the 8th European Conference on Combinatorics, Graph Theory and Applications (EuroComb\u201915), vol. 49, pp. 505\u2013512 (2015)","DOI":"10.1016\/j.endm.2015.06.070"},{"key":"9995_CR27","volume-title":"Polytopes, Graphs and Optimisation","author":"VA Yemelichev","year":"1984","unstructured":"Yemelichev, V.A., Koval\u00ebv, M.M., Kravtsov, M.K.: Polytopes, Graphs and Optimisation. Cambridge University Press, Cambridge (1984)"},{"key":"9995_CR28","unstructured":"Yusun, T.J.: On the Circuit Diameter of Polyhedra. Ph.D.\u00a0thesis, Simon Fraser University, Burnaby (2017)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-018-9995-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-9995-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-9995-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T23:09:44Z","timestamp":1556060984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-018-9995-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,24]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["9995"],"URL":"https:\/\/doi.org\/10.1007\/s00454-018-9995-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,24]]},"assertion":[{"value":"11 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}