{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:24:16Z","timestamp":1761805456597,"version":"3.37.3"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T00:00:00Z","timestamp":1600041600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T00:00:00Z","timestamp":1600041600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00453-020-00756-w","type":"journal-article","created":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T07:02:45Z","timestamp":1600066965000},"page":"252-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Distance and Routing Labeling Schemes for Cube-Free Median Graphs"],"prefix":"10.1007","volume":"83","author":[{"given":"Victor","family":"Chepoi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0162-1899","authenticated-orcid":false,"given":"Arnaud","family":"Labourel","sequence":"additional","affiliation":[]},{"given":"S\u00e9bastien","family":"Ratel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,14]]},"reference":[{"key":"756_CR1","doi-asserted-by":"publisher","first-page":"22:1","DOI":"10.1145\/2818694","volume":"12","author":"I Abraham","year":"2016","unstructured":"Abraham, I., Chechik, S., Gavoille, C., Peleg, D.: Forbidden-set distance labels for graphs of bounded doubling dimension. ACM Trans. Algorithms 12, 22:1\u201322:17 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"756_CR2","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In 26th IEEE International Conference on Distributed Computing Systems, ICDCS, IEEE Computer Society, p.\u00a075 (2006)"},{"key":"756_CR3","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. Intl. J. Robot. Res. 23, 811\u2013826 (2004)","journal-title":"Intl. J. Robot. Res."},{"key":"756_CR4","unstructured":"Agol, I.: The virtual Haken conjecture. Doc. Math., 18, 1045\u20131087 (With an appendix by Agol, Daniel Groves, and Jason Manning) (2013). http:\/\/www.emis.de\/journals\/DMJDMV\/vol-18\/33.html"},{"key":"756_CR5","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Gavoille, C., Halvorsen, E.B., Petersen, H.: Simpler, faster and shorter labels for distances in graphs. In: SODA, pp. 338\u2013350 (2016)","DOI":"10.1137\/1.9781611974331.ch25"},{"key":"756_CR6","unstructured":"Alstrup, S., G\u00f8rtz, I.L., Halvorsen, E.B., Porat, E.: Distance labeling schemes for trees. In: ICALP, pp. 132:1\u2013132:16 (2016)"},{"key":"756_CR7","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/jgt.3190080407","volume":"8","author":"H-J Bandelt","year":"1984","unstructured":"Bandelt, H.-J.: Retracts of hypercubes. J. Graph Theory 8, 501\u2013510 (1984)","journal-title":"J. Graph Theory"},{"key":"756_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1090\/conm\/453\/08795","volume":"453","author":"H-J Bandelt","year":"2008","unstructured":"Bandelt, H.-J., Chepoi, V.: Metric graph theory and geometry: a survey. Contemp. Math. 453, 49\u201386 (2008)","journal-title":"Contemp. Math."},{"key":"756_CR9","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1007\/s00454-015-9743-5","volume":"54","author":"H-J Bandelt","year":"2015","unstructured":"Bandelt, H.-J., Chepoi, V., Eppstein, D.: Ramified rectilinear polygons: coordinatization by dendrons. Discr. Comput. Geom. 54, 771\u2013797 (2015)","journal-title":"Discr. Comput. Geom."},{"key":"756_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0012-365X(83)90173-5","volume":"45","author":"H-J Bandelt","year":"1983","unstructured":"Bandelt, H.-J., Hedl\u00edkov\u00e1, J.: Median algebras. Discr. Math. 45, 1\u201330 (1983)","journal-title":"Discr. Math."},{"key":"756_CR11","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1112\/plms\/s3-58.3.439","volume":"s3\u201358","author":"H-J Bandelt","year":"1989","unstructured":"Bandelt, H.-J., van\u00a0de Vel, M.: Embedding topological median algebras in products of dendrons. Proc. Lond. Math. Soc. s3\u201358, 439\u2013453 (1989)","journal-title":"Proc. Lond. Math. Soc."},{"key":"756_CR12","doi-asserted-by":"publisher","first-page":"3465","DOI":"10.1016\/j.disc.2007.12.091","volume":"309","author":"F Bazzaro","year":"2009","unstructured":"Bazzaro, F., Gavoille, C.: Localized and compact data-structure for comparability graphs. Discr. Math. 309, 3465\u20133484 (2009)","journal-title":"Discr. Math."},{"key":"756_CR13","unstructured":"B\u00e9n\u00e9teau, L., Chalopin, J., Chepoi, V., Vax\u00e8s, Y.: Medians in median graphs and their cube complexes in linear time. In: ICALP, pp. 10:1\u201310:17 (2020)"},{"key":"756_CR14","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, 733\u2013767 (2001)","journal-title":"Adv. Appl. Math."},{"key":"756_CR15","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/0022-247X(67)90082-0","volume":"20","author":"MA Breuer","year":"1967","unstructured":"Breuer, M.A., Folkman, J.: An unexpected result in coding the vertices of a graph. J. Math. Anal. Appl. 20, 583\u2013600 (1967)","journal-title":"J. Math. Anal. Appl."},{"key":"756_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.disc.2004.09.018","volume":"307","author":"B Bre\u0161ar","year":"2007","unstructured":"Bre\u0161ar, B., Klav\u017ear, S., \u0160krekovski, R.: On cube-free median graphs. Discrete Math. 307, 345\u2013351 (2007)","journal-title":"Discrete Math."},{"key":"756_CR17","doi-asserted-by":"crossref","unstructured":"Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature. Grundlehren der mathematischen Wissenschaften, vol. 319, Springer, Berlin (1999)","DOI":"10.1007\/978-3-662-12494-9"},{"key":"756_CR18","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jcss.2020.05.001","volume":"113","author":"J Chalopin","year":"2020","unstructured":"Chalopin, J., Chepoi, V.: A counterexample to Thiagarajan\u2019s conjecture on regular event structures. J. Comput. Syst. Sci. 113, 76\u2013100 (2020)","journal-title":"J. Comput. Syst. Sci."},{"key":"756_CR19","unstructured":"Chalopin, J., Chepoi, V., Hirai, H., Osajda, D.: Weakly modular graphs and nonpositive curvature. Memoirs of AMS, (to appear)"},{"key":"756_CR20","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0012-365X(00)00183-7","volume":"226","author":"M Chastand","year":"2001","unstructured":"Chastand, M.: Fiber-complemented graphs. I. Struct. Invariant Subgr. Discrete Math. 226, 107\u2013141 (2001)","journal-title":"Struct. Invariant Subgr. Discrete Math."},{"key":"756_CR21","first-page":"75","volume":"49","author":"V Chepoi","year":"1989","unstructured":"Chepoi, V.: Classification of graphs by means of metric triangles. Metody Diskret. Anal. 49, 75\u201393 (1989)","journal-title":"Metody Diskret. Anal."},{"key":"756_CR22","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 CAT(0) complexes. Adv. Appl. Math. 24, 125\u2013179 (2000)","journal-title":"Adv. Appl. Math."},{"key":"756_CR23","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1137\/110837760","volume":"41","author":"V Chepoi","year":"2012","unstructured":"Chepoi, V.: Nice labeling problem for event structures: a counterexample. SIAM J. Comput. 41, 715\u2013727 (2012)","journal-title":"SIAM J. Comput."},{"key":"756_CR24","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.jalgor.2004.07.011","volume":"61","author":"V Chepoi","year":"2006","unstructured":"Chepoi, V., Dragan, F.F., Vax\u00e8s, Y.: Distance and routing labeling schemes for non-positively curved plane graphs. J. Algorithms 61, 60\u201388 (2006)","journal-title":"J. Algorithms"},{"key":"756_CR25","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1016\/j.jctb.2013.04.003","volume":"103","author":"V Chepoi","year":"2013","unstructured":"Chepoi, V., Hagen, M.F.: Distance and routing labeling schemes for non-positively curved plane graphs. J. Combin. Theory Ser. B 103, 428\u2013467 (2013)","journal-title":"J. Combin. Theory Ser. B"},{"key":"756_CR26","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1002\/jgt.22469","volume":"93","author":"V Chepoi","year":"2020","unstructured":"Chepoi, V., Labourel, A., Ratel, S.: On density of subgraphs of Cartesian products. J. Graph Theory 93, 64\u201387 (2020)","journal-title":"J. Graph Theory"},{"key":"756_CR27","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, 51\u201364 (2013)","journal-title":"Comput. Geom."},{"key":"756_CR28","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, New York (2009)","edition":"3"},{"key":"756_CR29","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0166-218X(02)00421-3","volume":"131","author":"B Courcelle","year":"2003","unstructured":"Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discrete Appl. Math. 131, 129\u2013150 (2003)","journal-title":"Discrete Appl. Math."},{"key":"756_CR30","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00453-008-9194-y","volume":"57","author":"FF Dragan","year":"2010","unstructured":"Dragan, F.F., Yan, C.: Collective tree spanners in graphs with bounded parameters. Algorithmica 57, 22\u201343 (2010)","journal-title":"Algorithmica"},{"key":"756_CR31","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: ICALP, Springer, pp. 757\u2013772 (2001)","DOI":"10.1007\/3-540-48224-5_62"},{"key":"756_CR32","doi-asserted-by":"crossref","unstructured":"Freedman, O., Gawrychowski, P., Nicholson, P.\u00a0K., Weimann, O.: Optimal distance labeling schemes for trees. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, ACM, pp. 185\u2013194 (2017)","DOI":"10.1145\/3087801.3087804"},{"key":"756_CR33","doi-asserted-by":"crossref","unstructured":"Gavoille, C., Ly, O.: Distance labeling in hyperbolic graphs. In: International Symposium on Algorithms and Computation, Springer, pp. 1071\u20131079 (2005)","DOI":"10.1007\/11602613_106"},{"key":"756_CR34","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0012-365X(03)00232-2","volume":"273","author":"C Gavoille","year":"2003","unstructured":"Gavoille, C., Paul, C.: Distance labeling scheme and split decomposition. Discrete Math. 273, 115\u2013130 (2003)","journal-title":"Discrete Math."},{"key":"756_CR35","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.1137\/050635006","volume":"22","author":"C Gavoille","year":"2008","unstructured":"Gavoille, C., Paul, C.: Optimal distance labeling for interval graphs and related graph families. SIAM J. Discrete Math. 22, 1239\u20131258 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"756_CR36","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53, 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"756_CR37","doi-asserted-by":"crossref","unstructured":"Gavoille, C., P\u00e9renn\u00e8s, S.: Memory requirement for routing in distributed networks. In: PODC, ACM, pp. 125\u2013133 (1996)","DOI":"10.1145\/248052.248075"},{"key":"756_CR38","unstructured":"Gawrychowski, P., Uznanski, P.: A note on distance labeling in planar graphs. CoRR, abs\/1611.06529, (2016)"},{"key":"756_CR39","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.aam.2005.08.009","volume":"38","author":"R Ghirst","year":"2007","unstructured":"Ghirst, R., Peterson, V.: The geometry and topology of reconfiguration. Adv. Appl. Math. 38, 302\u2013323 (2007)","journal-title":"Adv. Appl. Math."},{"key":"756_CR40","doi-asserted-by":"crossref","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.), Essays in Group Theory, Mathematical Sciences Research Institute Publications, vol. 8, Springer, New York, pp. 75\u2013263 (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"756_CR41","unstructured":"Hayashi, K.: A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes. In: ICALP, pp. 78:1\u201378:14 (2018)"},{"key":"756_CR42","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5, 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"756_CR43","first-page":"103","volume":"30","author":"S Klav\u017ear","year":"1999","unstructured":"Klav\u017ear, S., Mulder, H.M.: Median graphs: characterizations, location theory and related structures. J. Combin. Math. Combin. Comput. 30, 103\u2013127 (1999)","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"756_CR44","unstructured":"Knuth, D.E.: The Art of Computer Programming: Fascicle 0, Introduction to Combinatorial Algorithms and Boolean Functions, vol. 4, Addison-Wesley, Boston, MA (2008)"},{"key":"756_CR45","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Optimal scale-free compact routing schemes in networks of low doubling dimension. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, SIAM, pp. 939\u2013948 (2007). http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283484"},{"key":"756_CR46","unstructured":"Mulder, H.M.: The Interval Function of a Graph. Mathematical Centre Tracts, vol. 132, Mathematisch Centrum, Amsterdam (1980)"},{"key":"756_CR47","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(79)90151-1","volume":"25","author":"HM Mulder","year":"1979","unstructured":"Mulder, H.M., Schrijver, A.: Median graphs and Helly hypergraphs. Discrete Math. 25, 41\u201350 (1979)","journal-title":"Discrete Math."},{"key":"756_CR48","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, 2\u201313 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"756_CR49","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"756_CR50","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33, 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"key":"756_CR51","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/j.tcs.2005.03.015","volume":"340","author":"D Peleg","year":"2005","unstructured":"Peleg, D.: Informative labeling schemes for graphs. Theor. Comput. Sci. 340, 577\u2013593 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"756_CR52","volume-title":"Poc sets, median algebras, and group actions","author":"M Roller","year":"1998","unstructured":"Roller, M.: Poc sets, median algebras, and group actions. University of Southampton, Technical Report (1998)"},{"key":"756_CR53","unstructured":"Sageev, M.: CAT(0) cube complexes and groups. In: Bestvina, M., Sageev, M., Vogtmann, K. (eds.) Geometric Group Theory, IAS\/Park City Mathematics Series, vol. 21, AMS, IAS, pp. 6\u201353 (2012)"},{"key":"756_CR54","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"756_CR55","doi-asserted-by":"publisher","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC, ACM, pp. 281\u2013290 (2004). https:\/\/doi.org\/10.1145\/1007352.1007399","DOI":"10.1145\/1007352.1007399"},{"key":"756_CR56","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, ACM, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"756_CR57","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF02579350","volume":"3","author":"PM Winkler","year":"1983","unstructured":"Winkler, P.M.: Proof of the squashed cube conjecture. Combinatorica 3, 135\u2013139 (1983)","journal-title":"Combinatorica"},{"key":"756_CR58","doi-asserted-by":"crossref","unstructured":"Winskel, G., Nielsen, M.: Models for concurrency. In: Abramsky, S., Gabbay, D.M., Maibaum, T.S.E (eds), Handbook of Logic in Computer Science, vol. 4, Oxford University Press, , pp. 1\u2013148 (1995)","DOI":"10.1093\/oso\/9780198537809.003.0001"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00756-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00756-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00756-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T19:09:01Z","timestamp":1723576141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00756-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,14]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["756"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00756-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,9,14]]},"assertion":[{"value":"26 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}