{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T21:00:58Z","timestamp":1773954058856,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T00:00:00Z","timestamp":1574812800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T00:00:00Z","timestamp":1574812800000},"content-version":"vor","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":[[2021,4]]},"DOI":"10.1007\/s00454-019-00154-2","type":"journal-article","created":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T18:02:57Z","timestamp":1574877777000},"page":"636-654","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes"],"prefix":"10.1007","volume":"65","author":[{"given":"Koyo","family":"Hayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,27]]},"reference":[{"issue":"7\u20138","key":"154_CR1","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1177\/0278364904045468","volume":"23","author":"A Abrams","year":"2004","unstructured":"Abrams, A., Ghrist, R.: State complexes for metamorphic robots. Int. J. Robot. Res. 23(7\u20138), 811\u2013826 (2004)","journal-title":"Int. J. Robot. Res."},{"issue":"1","key":"154_CR2","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.aam.2011.06.004","volume":"48","author":"F Ardila","year":"2012","unstructured":"Ardila, F., Owen, M., Sullivant, S.: Geodesics in CAT(0) cubical complexes. Adv. Appl. Math. 48(1), 142\u2013163 (2012)","journal-title":"Adv. Appl. Math."},{"key":"154_CR3","volume-title":"Convex Analysis and Optimization in Hadamard Spaces. De Gruyter Series in Nonlinear Analysis and Applications","author":"M Ba\u010d\u00e1k","year":"2014","unstructured":"Ba\u010d\u00e1k, M.: Convex Analysis and Optimization in Hadamard Spaces. De Gruyter Series in Nonlinear Analysis and Applications, vol. 22. De Gruyter, Berlin (2014)"},{"key":"154_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1090\/conm\/453\/08795","volume-title":"Surveys on Discrete and Computational Geometry: Twenty Years Later. Contemporary Mathematics","author":"H-J Bandelt","year":"2008","unstructured":"Bandelt, H.-J., Chepoi, V.: Metric graph theory and geometry: a survey. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Surveys on Discrete and Computational Geometry: Twenty Years Later. Contemporary Mathematics, vol. 453, pp. 49\u201386. American Mathematical Society, Providence (2008)"},{"issue":"1","key":"154_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1093\/oxfordjournals.molbev.a026036","volume":"16","author":"H-J Bandelt","year":"1999","unstructured":"Bandelt, H.-J., Forster, P., R\u00f6hl, A.: Median-joining networks for inferring intraspecific phylogenies. Mol. Biol. Evol. 16(1), 37\u201348 (1999)","journal-title":"Mol. Biol. Evol."},{"issue":"2","key":"154_CR6","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0097-3165(91)90044-H","volume":"57","author":"H-J Bandelt","year":"1991","unstructured":"Bandelt, H.-J., van de Vel, M.: Superextensions and the depth of median graphs. J. Comb. Theory Ser. A 57(2), 187\u2013202 (1991)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"1\u20133","key":"154_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(93)90140-O","volume":"111","author":"J-P Barth\u00e9l\u00e9my","year":"1993","unstructured":"Barth\u00e9l\u00e9my, J.-P., Constantin, J.: Median graphs, parallelism and posets. Discrete Math. 111(1\u20133), 49\u201363 (1993)","journal-title":"Discrete Math."},{"issue":"4","key":"154_CR8","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1006\/aama.2001.0759","volume":"27","author":"LJ Billera","year":"2001","unstructured":"Billera, L.J., Holmes, S.P., Vogtmann, K.: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27(4), 733\u2013767 (2001)","journal-title":"Adv. Appl. Math."},{"key":"154_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-Positive Curvature. Grundlehren der Mathematischen Wissenschaften,","author":"M Bridson","year":"1999","unstructured":"Bridson, M., Haefliger, A.: Metric Spaces of Non-Positive Curvature. Grundlehren der Mathematischen Wissenschaften, vol. 319. Springer, Berlin (1999)"},{"key":"154_CR10","doi-asserted-by":"crossref","unstructured":"Canny, J., Reif, J.: New lower bound techniques for robot motion planning problems. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pp. 49\u201360. IEEE (1987)","DOI":"10.1109\/SFCS.1987.42"},{"issue":"2","key":"154_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1006\/aama.1999.0677","volume":"24","author":"V Chepoi","year":"2000","unstructured":"Chepoi, V.: Graphs of some $${\\rm CAT}(0)$$ complexes. Adv. Appl. Math. 24(2), 125\u2013179 (2000)","journal-title":"Adv. Appl. Math."},{"issue":"1","key":"154_CR12","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.comgeo.2012.04.002","volume":"46","author":"V Chepoi","year":"2013","unstructured":"Chepoi, V., Maftuleac, D.: Shortest path problem in rectangular complexes of global nonpositive curvature. Comput. Geom. 46(1), 51\u201364 (2013)","journal-title":"Comput. Geom."},{"issue":"3","key":"154_CR13","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/BF01232283","volume":"105","author":"SM Gersten","year":"1991","unstructured":"Gersten, S.M., Short, H.: Small cancellation theory and automatic groups II. Invent. Math. 105(3), 641\u2013662 (1991)","journal-title":"Invent. Math."},{"issue":"5","key":"154_CR14","doi-asserted-by":"publisher","first-page":"1697","DOI":"10.1137\/040609860","volume":"45","author":"R Ghrist","year":"2006","unstructured":"Ghrist, R., LaValle, S.M.: Nonpositive curvature and Pareto optimal coordination of robots. SIAM J. Control Optim. 45(5), 1697\u20131713 (2006)","journal-title":"SIAM J. Control Optim."},{"issue":"3","key":"154_CR15","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.aam.2005.08.009","volume":"38","author":"R Ghrist","year":"2007","unstructured":"Ghrist, R., Peterson, V.: The geometry and topology of reconfiguration. Adv. Appl. Math. 38(3), 302\u2013323 (2007)","journal-title":"Adv. Appl. Math."},{"key":"154_CR16","first-page":"75","volume-title":"Essays in Group Theory. Mathematical Sciences Research Institute Publications","author":"M Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8, pp. 75\u2013263. Springer, New York (1987)"},{"key":"154_CR17","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.aam.2015.04.002","volume":"68","author":"E Miller","year":"2015","unstructured":"Miller, E., Owen, M., Provan, J.S.: Polyhedral computational geometry for averaging metric phylogenetic trees. Adv. Appl. Math. 68, 51\u201391 (2015)","journal-title":"Adv. Appl. Math."},{"key":"154_CR18","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","volume-title":"Handbook of Computational Geometry","author":"JSB Mitchell","year":"2000","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633\u2013701. Elsevier, Amsterdam (2000)"},{"key":"154_CR19","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B., Sharir, M.: New results on shortest paths in three dimensions. In: Proceedings of the 20th Annual Symposium on Computational Geometry (SCG\u201904), pp. 124\u2013133. ACM, New York (2004)","DOI":"10.1145\/997817.997839"},{"key":"154_CR20","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0012-365X(78)90199-1","volume":"24","author":"M Mulder","year":"1978","unstructured":"Mulder, M.: The structure of median graphs. Discrete Math. 24, 197\u2013204 (1978)","journal-title":"Discrete Math."},{"issue":"1","key":"154_CR21","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(81)90112-2","volume":"13","author":"M Nielsen","year":"1981","unstructured":"Nielsen, M., Plotkin, G., Winskel, G.: Petri nets, event structures and domains, part I. Theoret. Comput. Sci. 13(1), 85\u2013108 (1981)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"154_CR22","doi-asserted-by":"publisher","first-page":"1506","DOI":"10.1137\/090751396","volume":"25","author":"M Owen","year":"2011","unstructured":"Owen, M.: Computing geodesic distances in tree space. SIAM J. Discrete Math. 25(4), 1506\u20131529 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"154_CR23","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TCBB.2010.3","volume":"8","author":"M Owen","year":"2011","unstructured":"Owen, M., Provan, J.S.: A fast algorithm for computing geodesic distances in tree space. IEEE\/ACM Trans. Comput. Biol. Bioinform. 8(1), 2\u201313 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"154_CR24","unstructured":"Polishchuk, V., Mitchell, J.S.B.: Touring convex bodies\u2014A conic programming solution. In: Proceedings of the 17th Canadian Conference on Computational Geometry, pp. 101\u2013104 (2005)"},{"key":"154_CR25","unstructured":"Roller, M.: Poc sets, median algebras and group actions (2016). arXiv:1607.07747"},{"issue":"3","key":"154_CR26","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1112\/plms\/s3-71.3.585","volume":"71","author":"M Sageev","year":"1995","unstructured":"Sageev, M.: Ends of groups pairs and non-positively curved cube complexes. Proc. Lond. Math. Soc. 71(3), 585\u2013617 (1995)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"3","key":"154_CR27","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/0216038","volume":"16","author":"A Sharir","year":"1987","unstructured":"Sharir, A.: On shortest paths amidst convex polyhedra. SIAM J. Comput. 16(3), 561\u2013572 (1987)","journal-title":"SIAM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00154-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00154-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00154-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,5]],"date-time":"2021-03-05T20:11:27Z","timestamp":1614975087000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00154-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,27]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["154"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00154-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,27]]},"assertion":[{"value":"31 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}