{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:20:15Z","timestamp":1772119215042,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,4]],"date-time":"2023-12-04T00:00:00Z","timestamp":1701648000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,4]],"date-time":"2023-12-04T00:00:00Z","timestamp":1701648000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Romanian Ministry of Research, Innovation and Digitalization","award":["CCCDI - UEFISCDI"],"award-info":[{"award-number":["CCCDI - UEFISCDI"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1007\/s00224-023-10153-9","type":"journal-article","created":{"date-parts":[[2023,12,4]],"date-time":"2023-12-04T01:01:35Z","timestamp":1701651695000},"page":"144-193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs"],"prefix":"10.1007","volume":"68","author":[{"given":"Pierre","family":"Berg\u00e9","sequence":"first","affiliation":[]},{"given":"Guillaume","family":"Ducoffe","sequence":"additional","affiliation":[]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,4]]},"reference":[{"key":"10153_CR1","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1090\/S0002-9939-1961-0125807-5","volume":"12","author":"SP Avann","year":"1961","unstructured":"Avann, S.P.: Metric ternary distributive semi-lattices. Proc. Amer. Math. Soc. 12, 407\u2013414 (1961)","journal-title":"Proc. Amer. Math. Soc."},{"key":"10153_CR2","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1090\/S0002-9904-1947-08864-9","volume":"53","author":"G Birkhoff","year":"1947","unstructured":"Birkhoff, G., Kiss, S.A.: A ternary operation in distributive lattices. Bull. Amer. Math. Soc. 53, 745\u2013752 (1947)","journal-title":"Bull. Amer. Math. Soc."},{"key":"10153_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1090\/conm\/453\/08795","volume":"453","author":"H Bandelt","year":"2008","unstructured":"Bandelt, H., Chepoi, V.: Metric graph theory and geometry: a survey. Contemp. Math. 453, 49\u201386 (2008)","journal-title":"Contemp. Math."},{"issue":"2","key":"10153_CR4","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(2), 125\u2013179 (2000)","journal-title":"Adv. Appl. Math."},{"issue":"1\u20133","key":"10153_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(93)90140-O","volume":"111","author":"J Barth\u00e9lemy","year":"1993","unstructured":"Barth\u00e9lemy, J., Constantin, J.: Median graphs, parallelism and posets. Discret. Math. 111(1\u20133), 49\u201363 (1993)","journal-title":"Discret. Math."},{"key":"10153_CR6","doi-asserted-by":"crossref","unstructured":"Sassone, V., Nielsen, M., Winskel, G.: A classification of models for concurrency. In: Proc. of CONCUR. Lecture Notes in Computer Science, vol. 715, pp. 82\u201396 (1993)","DOI":"10.1007\/3-540-57208-2_7"},{"key":"10153_CR7","doi-asserted-by":"publisher","first-page":"1150","DOI":"10.1086\/344397","volume":"71","author":"H Bandelt","year":"2002","unstructured":"Bandelt, H., Quintana-Murci, L., Salas, A., Macaulay, V.: The fingerprint of phantom mutations in mitochondrial dna data. Am. J. Hum. Genet. 71, 1150\u20131160 (2002)","journal-title":"Am. J. Hum. Genet."},{"issue":"2","key":"10153_CR8","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1093\/genetics\/141.2.743","volume":"141","author":"HJ Bandelt","year":"1995","unstructured":"Bandelt, H.J., Forster, P., Sykes, B.C., Richards, M.B.: Mitochondrial portraits of human populations using median networks. Genetics 141(2), 743\u2013753 (1995)","journal-title":"Genetics"},{"key":"10153_CR9","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proc. of SODA, pp. 377\u2013391 (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"10153_CR10","doi-asserted-by":"crossref","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In: Proc. of SODA, pp. 2143\u20132152 (2017)","DOI":"10.1137\/1.9781611974782.139"},{"issue":"5","key":"10153_CR11","doi-asserted-by":"publisher","first-page":"1506","DOI":"10.1137\/20m136551x","volume":"51","author":"G Ducoffe","year":"2022","unstructured":"Ducoffe, G., Habib, M., Viennot, L.: Diameter, eccentricities and distance oracle computations on H -minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension. SIAM J. Comput. 51(5), 1506\u20131534 (2022). https:\/\/doi.org\/10.1137\/20m136551x","journal-title":"SIAM J. Comput."},{"key":"10153_CR12","doi-asserted-by":"crossref","unstructured":"Chechik, S., Larkin, D.H., Roditty, L., Schoenebeck, G., Tarjan, R.E., Williams, V.V.: Better approximation algorithms for the graph diameter. In: Proc. of SODA, pp. 1041\u20131052 (2014)","DOI":"10.1137\/1.9781611973402.78"},{"key":"10153_CR13","doi-asserted-by":"crossref","unstructured":"Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proc. of STOC, pp. 515\u2013524 (2013)","DOI":"10.1145\/2488608.2488673"},{"issue":"2","key":"10153_CR14","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. Discret. Math. 24(2), 197\u2013204 (1978)","journal-title":"Discret. Math."},{"key":"10153_CR15","volume-title":"The interval function of a graph","author":"M Mulder","year":"1980","unstructured":"Mulder, M.: The interval function of a graph. Mathematical Centre Tracts, Mathematisch Centrum, Amsterdam (1980)"},{"issue":"4","key":"10153_CR16","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/jgt.3190080407","volume":"8","author":"H Bandelt","year":"1984","unstructured":"Bandelt, H.: Retracts of hypercubes. J. Graph Theory 8(4), 501\u2013510 (1984)","journal-title":"J. Graph Theory"},{"issue":"1","key":"10153_CR17","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. Discret. Math. 25(1), 41\u201350 (1979)","journal-title":"Discret. Math."},{"issue":"1\u20133","key":"10153_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0012-365X(98)00019-3","volume":"187","author":"S Klavzar","year":"1998","unstructured":"Klavzar, S., Mulder, H.M., Skrekovski, R.: An Euler-type formula for median graphs. Discret. Math. 187(1\u20133), 255\u2013258 (1998)","journal-title":"Discret. Math."},{"key":"10153_CR19","unstructured":"B\u00e9n\u00e9teau, L., Chalopin, J., Chepoi, V., Vax\u00e8s, Y.: Medians in median graphs and their cube complexes in linear time. In: Proc. of ICALP, vol. 168, pp. 10\u201311017 (2020)"},{"issue":"1\u20132","key":"10153_CR20","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(97)00136-9","volume":"215","author":"J Hagauer","year":"1999","unstructured":"Hagauer, J., Imrich, W., Klavzar, S.: Recognizing median graphs in subquadratic time. Theor. Comput. Sci. 215(1\u20132), 123\u2013136 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10153_CR21","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/S0895480197323494","volume":"12","author":"W Imrich","year":"1999","unstructured":"Imrich, W., Klavzar, S., Mulder, H.M.: Median graphs and triangle-free graphs. SIAM J. Discret. Math. 12(1), 111\u2013118 (1999)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"10153_CR22","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"10153_CR23","unstructured":"Chepoi, V., Dragan, F.F., Vax\u00e8s, Y.: Center and diameter problems in plane triangulations and quadrangulations. In: Proc. of SODA, pp. 346\u2013 355 (2002)"},{"key":"10153_CR24","unstructured":"Ducoffe, G.: Isometric embeddings in trees and their use in distance problems. In: Proc. of MFCS. LIPIcs, vol. 202, pp. 43\u201314316 (2021)"},{"key":"10153_CR25","unstructured":"Chepoi, V., Labourel, A., Ratel, S.: Distance labeling schemes for cube-free median graphs. In: Proc. of MFCS, vol. 138, pp. 15\u201311514 (2019)"},{"key":"10153_CR26","doi-asserted-by":"crossref","unstructured":"Berg\u00e9, P., Habib, M.: Diameter, radius and all eccentricities in linear time for constant-dimension median graphs. In: Proc. of LAGOS (2021)","DOI":"10.1016\/j.procs.2021.11.015"},{"key":"10153_CR27","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01894188","volume":"3","author":"J Barth\u00e9lemy","year":"1986","unstructured":"Barth\u00e9lemy, J., Leclerc, B., Monjardet, B.: On the use of ordered sets in problems of comparison and consensus of classifications. J. Classif. 3, 187\u2013224 (1986)","journal-title":"J. Classif."},{"key":"10153_CR28","unstructured":"Gutman, R.J.: Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In: Proc. of ALENEX\/ANALC, pp. 100\u2013111 (2004)"},{"issue":"4","key":"10153_CR29","doi-asserted-by":"publisher","first-page":"1399","DOI":"10.1137\/090760301","volume":"24","author":"H Bandelt","year":"2010","unstructured":"Bandelt, H., Chepoi, V., Eppstein, D.: Combinatorics and geometry of finite and infinite squaregraphs. SIAM J. Discret. Math. 24(4), 1399\u20131440 (2010)","journal-title":"SIAM J. Discret. Math."},{"key":"10153_CR30","doi-asserted-by":"publisher","DOI":"10.1201\/b10959","volume-title":"Handbook of Product Graphs","author":"R Hammack","year":"2011","unstructured":"Hammack, R., Imrich, W., Klav\u017ear, S.: Handbook of Product Graphs. CRC Press, Boca Raton, FL (2011)"},{"key":"10153_CR31","doi-asserted-by":"crossref","unstructured":"Kovse, M.: Complexity of phylogenetic networks: counting cubes in median graphs and related problems. Analysis of complex networks: From Biology to Linguistics, 323\u2013350 (2009)","DOI":"10.1002\/9783527627981.ch13"},{"issue":"1\u20133","key":"10153_CR32","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0166-218X(98)00003-1","volume":"84","author":"FR McMorris","year":"1998","unstructured":"McMorris, F.R., Mulder, H.M., Roberts, F.S.: The median procedure on median graphs. Discret. Appl. Math. 84(1\u20133), 165\u2013181 (1998)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"10153_CR33","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1016\/j.ejc.2005.03.001","volume":"27","author":"H Bandelt","year":"2006","unstructured":"Bandelt, H., Chepoi, V., Dress, A.W.M., Koolen, J.H.: Combinatorics of lopsided sets. Eur. J. Comb. 27(5), 669\u2013689 (2006)","journal-title":"Eur. J. Comb."},{"key":"10153_CR34","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1112\/plms\/s3-58.3.439","volume":"58","author":"H Bandelt","year":"1989","unstructured":"Bandelt, H., van de Vel, M.: Embedding topological median algebras in products of dendrons. Proc. London Math. Soc. 58, 439\u2013453 (1989)","journal-title":"Proc. London Math. Soc."},{"issue":"2","key":"10153_CR35","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0895480101383202","volume":"15","author":"S Klavzar","year":"2002","unstructured":"Klavzar, S., Mulder, H.M.: Partial cubes and crossing graphs. SIAM J. Discret. Math. 15(2), 235\u2013251 (2002)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"10153_CR36","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1142\/S0129054199000125","volume":"10","author":"M Habib","year":"1999","unstructured":"Habib, M., Paul, C., Viennot, L.: Partition refinement techniques: An interesting algorithmic tool kit. Int. J. Found. Comput. Sci. 10(2), 147\u2013170 (1999)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"6","key":"10153_CR37","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10153_CR38","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0166-218X(84)90069-6","volume":"7","author":"PM Winkler","year":"1984","unstructured":"Winkler, P.M.: Isometric embedding in products of complete graphs. Discret. Appl. Math. 7(2), 221\u2013225 (1984)","journal-title":"Discret. Appl. Math."},{"key":"10153_CR39","doi-asserted-by":"crossref","unstructured":"Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: Proc. of SODA, pp. 1681\u20131697 (2015)","DOI":"10.1137\/1.9781611973730.112"},{"issue":"3","key":"10153_CR40","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1016\/j.ejc.2005.10.009","volume":"28","author":"B Bresar","year":"2007","unstructured":"Bresar, B.: Characterizing almost-median graphs. Eur. J. Comb. 28(3), 916\u2013920 (2007)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"10153_CR41","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1016\/j.disc.2011.09.008","volume":"312","author":"S Klavzar","year":"2012","unstructured":"Klavzar, S., Shpectorov, S.V.: Characterizing almost-median graphs II. Discret. Math. 312(2), 462\u2013464 (2012)","journal-title":"Discret. Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10153-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10153-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10153-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T06:04:56Z","timestamp":1706767496000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10153-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,4]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10153"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10153-9","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2233141\/v1","asserted-by":"object"}]},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,4]]},"assertion":[{"value":"13 November 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}