{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T11:03:52Z","timestamp":1775473432360,"version":"3.50.1"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-CE48-0001"],"award-info":[{"award-number":["ANR-22-CE48-0001"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-CE48-0001"],"award-info":[{"award-number":["ANR-22-CE48-0001"]}],"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":[[2026,2]]},"DOI":"10.1007\/s00453-025-01344-6","type":"journal-article","created":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T05:34:23Z","timestamp":1765172063000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs"],"prefix":"10.1007","volume":"88","author":[{"given":"Feodor","family":"Dragan","sequence":"first","affiliation":[]},{"given":"Guillaume","family":"Ducoffe","sequence":"additional","affiliation":[]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[]},{"given":"Laurent","family":"Viennot","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,8]]},"reference":[{"key":"1344_CR1","doi-asserted-by":"publisher","unstructured":"Roditty, Liam, Williams, Virginia\u00a0Vassilevska.: Fast approximation algorithms for the diameter and radius of sparse graphs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1-4, 2013, pp. 515\u2013524. ACM, (2013). https:\/\/doi.org\/10.1145\/2488608.2488673","DOI":"10.1145\/2488608.2488673"},{"key":"1344_CR2","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Robert Krauthgamer, editor, In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 377\u2013391. SIAM, (2016). URL: https:\/\/doi.org\/10.1137\/1.9781611974331.ch28,","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"1344_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.tcs.2015.02.033","volume":"586","author":"M Borassi","year":"2015","unstructured":"Borassi, M., Crescenzi, P., Habib, M., Kosters, W.A., Marino, A., Takes, F.W.: Fast diameter and radius bfs-based computation in (weakly connected) real-world graphs: with an application to the six degrees of separation games. Theor. Comput. Sci. 586, 59\u201380 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.02.033","journal-title":"Theor. Comput. Sci."},{"key":"1344_CR4","doi-asserted-by":"publisher","unstructured":"Frank\u00a0W., Takes, Walter\u00a0A, Kosters, Determining the diameter of small world networks. In Craig Macdonald, Iadh Ounis, and Ian Ruthven, editors, Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United Kingdom, October 24-28, 2011, pp. 1191\u20131196. ACM, (2011). https:\/\/doi.org\/10.1145\/2063576.2063748","DOI":"10.1145\/2063576.2063748"},{"key":"1344_CR5","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.tcs.2012.09.018","volume":"514","author":"P Crescenzi","year":"2013","unstructured":"Crescenzi, P., Grossi, R., Habib, M., Lanzi, L., Marino, A.: On computing the diameter of real-world undirected graphs. Theor. Comput. Sci. 514, 84\u201395 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.09.018","journal-title":"Theor. Comput. Sci."},{"key":"1344_CR6","doi-asserted-by":"publisher","unstructured":"Akiba, Takuya, Iwata, Yoichi, Kawata, Yuki. An exact algorithm for diameters of large real directed graphs. In Evripidis Bampis, editor, Experimental Algorithms - 14th International Symposium, SEA 2015, Paris, France, June 29 - July 1, 2015, Proceedings, volume 9125 of Lecture Notes in Computer Science, pp. 56\u201367. Springer, (2015). https:\/\/doi.org\/10.1007\/978-3-319-20086-6_5","DOI":"10.1007\/978-3-319-20086-6_5"},{"key":"1344_CR7","doi-asserted-by":"publisher","unstructured":"Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. Four degrees of separation. In Noshir\u00a0S. Contractor, Brian Uzzi, Michael\u00a0W. Macy, and Wolfgang Nejdl, editors, Web Science 2012, WebSci \u201912, Evanston, IL, USA - June 22 - 24, 2012, pp. 33\u201342. ACM, (2012). https:\/\/doi.org\/10.1145\/2380718.2380723","DOI":"10.1145\/2380718.2380723"},{"key":"1344_CR8","doi-asserted-by":"publisher","unstructured":"Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. Four degrees of separation. In Noshir\u00a0S. Contractor, Brian Uzzi, Michael\u00a0W. Macy, and Wolfgang Nejdl, editors, Web Science 2012, WebSci \u201912, Evanston, IL, USA - June 22 - 24, 2012, pp. 33\u201342. ACM, (2012). https:\/\/doi.org\/10.1145\/2380718.2380723","DOI":"10.1145\/2380718.2380723"},{"key":"1344_CR9","unstructured":"The Sage Developers. SageMath, the Sage Mathematics Software System (Version 10.6), diameter function in the Undirected graphs library, (2025). URL: https:\/\/doc.sagemath.org\/html\/en\/reference\/graphs\/sage\/graphs\/graph.html#sage.graphs.graph.Graph.diameter"},{"issue":"1","key":"1344_CR10","doi-asserted-by":"publisher","first-page":"100","DOI":"10.3390\/a6010100","volume":"6","author":"FW Takes","year":"2013","unstructured":"Takes, F.W., Kosters, W.A.: Computing the eccentricity distribution of large graphs. Algorithms 6(1), 100\u2013118 (2013). https:\/\/doi.org\/10.3390\/a6010100","journal-title":"Algorithms"},{"key":"1344_CR11","doi-asserted-by":"publisher","unstructured":"Michele Borassi, Pierluigi Crescenzi, and Luca Trevisan. An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. In Philip\u00a0N. Klein, editor, In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 920\u2013939. SIAM, (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.58","DOI":"10.1137\/1.9781611974782.58"},{"key":"1344_CR12","doi-asserted-by":"publisher","unstructured":"Marco\u00a0L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pp. 261\u2013270. ACM, (2016). https:\/\/doi.org\/10.1145\/2840728.2840746","DOI":"10.1145\/2840728.2840746"},{"key":"1344_CR13","doi-asserted-by":"publisher","unstructured":"Geisberger, Robert, Sanders, Peter, Schultes, Dominik, Delling, Daniel: Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Catherine\u00a0C. McGeoch, editor, Experimental Algorithms, In: 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30-June 1, 2008, Proceedings, volume 5038 of Lecture Notes in Computer Science, pp. 319\u2013333. Springer, (2008). https:\/\/doi.org\/10.1007\/978-3-540-68552-4_24","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"1344_CR14","doi-asserted-by":"publisher","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.F.: Hierarchical hub labelings for shortest paths. In Leah Epstein and Paolo Ferragina, editors, Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, volume 7501 of Lecture Notes in Computer Science, pp. 24\u201335. Springer, (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_4","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"1344_CR15","doi-asserted-by":"publisher","unstructured":"Sen, Sandeep, Muralidhara, V.N.: The covert set-cover problem with application to network discovery. In Md.\u00a0Saidur Rahman and Satoshi Fujita, editors, WALCOM: Algorithms and Computation, In: 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Proceedings, volume 5942 of Lecture Notes in Computer Science, pp. 228\u2013239. Springer, (2010). https:\/\/doi.org\/10.1007\/978-3-642-11440-3_21","DOI":"10.1007\/978-3-642-11440-3_21"},{"key":"1344_CR16","doi-asserted-by":"publisher","unstructured":"Magnien, Cl\u00e9mence, Latapy, Matthieu, Habib, Michel.: Fast computation of empirically tight bounds for the diameter of massive graphs. ACM J. Exp. Algorithmics,13, 1\u201310 (2008). https:\/\/doi.org\/10.1145\/1412228.1455266","DOI":"10.1145\/1412228.1455266"},{"key":"1344_CR17","doi-asserted-by":"publisher","unstructured":"Guillaume Ducoffe. Obstructions to faster diameter computation: Asteroidal sets. In Holger Dell and Jesper Nederlof, editors, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany, volume 249 of LIPIcs, pp. 10:1\u201310:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.10","DOI":"10.4230\/LIPIcs.IPEC.2022.10"},{"issue":"2","key":"1344_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/J.COSREV.2010.09.009","volume":"5","author":"RM McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying Algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011). https:\/\/doi.org\/10.1016\/J.COSREV.2010.09.009","journal-title":"Certifying Algorithms. Comput. Sci. Rev."},{"key":"1344_CR19","doi-asserted-by":"publisher","unstructured":"Alkassar, Eyad, B\u00f6hme, Sascha, Mehlhorn, Kurt, Rizkallah, Christine. Verification of certifying computations. In Ganesh Gopalakrishnan and Shaz Qadeer, editors, Computer Aided Verification - 23rd International Conference, CAV 2011, Snowbird, UT, USA, July 14-20, 2011. Proceedings, volume 6806 of Lecture Notes in Computer Science, pp. 67\u201382. Springer, (2011). https:\/\/doi.org\/10.1007\/978-3-642-22110-1_7","DOI":"10.1007\/978-3-642-22110-1_7"},{"key":"1344_CR20","doi-asserted-by":"publisher","unstructured":"K\u00fcnnemann, Marvin.: On nondeterministic derandomization of freivalds\u2019 algorithm: Consequences, avenues and algorithmic progress. In: Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pp. 56:1\u201356:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2018). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2018.56","DOI":"10.4230\/LIPICS.ESA.2018.56"},{"key":"1344_CR21","doi-asserted-by":"publisher","unstructured":"Funke, Stefan, Proissl, Claudius, Storandt, Sabine.: Computing the exact radius of large graphs. In Petra Mutzel and Nicola Prezza, editors, 23rd International Symposium on Experimental Algorithms, SEA 2025, July 22-24, 2025, Venice, Italy, volume 338 of LIPIcs, pp. 17:1\u201317:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2025). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2025.17","DOI":"10.4230\/LIPIcs.SEA.2025.17"},{"issue":"2","key":"1344_CR22","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"KL Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2), 488\u2013499 (1995). https:\/\/doi.org\/10.1145\/201019.201036","journal-title":"J. ACM"},{"key":"1344_CR23","doi-asserted-by":"publisher","unstructured":"Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New bounds for approximating extremal distances in undirected graphs. In Robert Krauthgamer, editor, In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 363\u2013376. SIAM, 2016. https:\/\/doi.org\/10.1137\/1.9781611974331.ch27","DOI":"10.1137\/1.9781611974331.ch27"},{"issue":"4","key":"1344_CR24","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167\u20131181 (1999). https:\/\/doi.org\/10.1137\/S0097539796303421","journal-title":"SIAM J. Comput."},{"key":"1344_CR25","doi-asserted-by":"publisher","unstructured":"Shiri Chechik, Daniel\u00a0H. Larkin, Liam Roditty, Grant Schoenebeck, Robert\u00a0Endre Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the graph diameter. In: Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 1041\u20131052. SIAM, (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.78","DOI":"10.1137\/1.9781611973402.78"},{"key":"1344_CR26","unstructured":"Li, Ray.: Improved seth-hardness of unweighted diameter. CoRR, abs\/2008.05106, (2020). arXiv:2008.05106"},{"key":"1344_CR27","doi-asserted-by":"publisher","unstructured":"\u00c9douard Bonnet. 4 vs 7 sparse undirected unweighted diameter is seth-hard at time n$$^{\\hat{\\,}}\\{4\/3\\}$$. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pp. 34:1\u201334:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2021). URL: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.34","DOI":"10.4230\/LIPIcs.ICALP.2021.34"},{"key":"1344_CR28","doi-asserted-by":"publisher","unstructured":"Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. Hardness of approximate diameter: Now for undirected graphs. J. ACM,72(1):6:1\u20136:32, (2025). https:\/\/doi.org\/10.1145\/3704631","DOI":"10.1145\/3704631"},{"key":"1344_CR29","doi-asserted-by":"crossref","unstructured":"Handler, Gabriel\u00a0Y.: Minimax location of a facility in an undirected tree graph. Transp. Sci.7(3):287\u2013293, (1973). URL: https:\/\/pubsonline.informs.org\/doi\/abs\/10.1287\/trsc.7.3.287","DOI":"10.1287\/trsc.7.3.287"},{"issue":"1","key":"1344_CR30","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1002\/net.21631","volume":"67","author":"Muad Abu-Ata","year":"2016","unstructured":"Abu-Ata, Muad, Dragan, Feodor F.: Metric tree-like structures in real-world networks: an empirical study. Networks 67(1), 49\u201368 (2016). https:\/\/doi.org\/10.1002\/net.21631","journal-title":"Networks"},{"key":"1344_CR31","doi-asserted-by":"publisher","unstructured":"Victor Chepoi, Feodor\u00a0F. Dragan, Bertrand Estellon, Michel Habib, and Yann Vax\u00e8s. Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. In: Monique Teillaud, editor, Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008, pp. 59\u201368. ACM, (2008). https:\/\/doi.org\/10.1145\/1377676.1377687","DOI":"10.1145\/1377676.1377687"},{"issue":"2","key":"1344_CR32","doi-asserted-by":"publisher","first-page":"393","DOI":"10.7155\/jgaa.00496","volume":"23","author":"V Chepoi","year":"2019","unstructured":"Chepoi, V., Dragan, F.F., Habib, M., Vax\u00e8s, Y., Alrasheed, H.: Fast approximation of eccentricities and distances in hyperbolic graphs. J. Graph Algorithms Appl. 23(2), 393\u2013433 (2019). https:\/\/doi.org\/10.7155\/jgaa.00496","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"1344_CR33","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/net.10098","volume":"42","author":"DG Corneil","year":"2003","unstructured":"Corneil, D.G., Dragan, F.F., K\u00f6hler, E.: On the power of BFS to determine a graph\u2019s diameter. Networks 42(4), 209\u2013222 (2003). https:\/\/doi.org\/10.1002\/net.10098","journal-title":"Networks"},{"key":"1344_CR34","doi-asserted-by":"publisher","unstructured":"Victor Chepoi and Bertrand Estellon. Packing and covering delta -hyperbolic spaces by balls. In Moses Charikar, Klaus Jansen, Omer Reingold, and Jos\u00e9 D.\u00a0P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, volume 4627 of Lecture Notes in Computer Science, pp. 59\u201373. Springer, (2007). https:\/\/doi.org\/10.1007\/978-3-540-74208-1_5","DOI":"10.1007\/978-3-540-74208-1_5"},{"issue":"1\u20133","key":"1344_CR35","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0012-365X(99)00337-4","volume":"218","author":"O Goodman","year":"2000","unstructured":"Goodman, O., Moulton, V.: On the tight span of an antipodal graph. Discret. Math. 218(1\u20133), 73\u201396 (2000)","journal-title":"Discret. Math."},{"key":"1344_CR36","doi-asserted-by":"publisher","unstructured":"Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David\u00a0B. Shmoys, editor, In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 624\u2013633. ACM, (2014). https:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"issue":"8","key":"1344_CR37","doi-asserted-by":"publisher","first-page":"2292","DOI":"10.1007\/s00453-020-00680-z","volume":"82","author":"K Bringmann","year":"2020","unstructured":"Bringmann, K., Husfeldt, T., Magnusson, M.: Multivariate analysis of orthogonal range searching and graph distances. Algorithmica 82(8), 2292\u20132315 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00680-z","journal-title":"Algorithmica"},{"issue":"1","key":"1344_CR38","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/0196-6774(80)90005-X","volume":"1","author":"L Monier","year":"1980","unstructured":"Monier, L.: Combinatorial solutions of multidimensional divide-and-conquer recurrences. J. Algorithms 1(1), 60\u201374 (1980). https:\/\/doi.org\/10.1016\/0196-6774(80)90005-X","journal-title":"J. Algorithms"},{"issue":"3","key":"1344_CR39","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1002\/net.21998","volume":"77","author":"G Ducoffe","year":"2021","unstructured":"Ducoffe, G., Dragan, F.F.: A story of diameter, radius, and (almost) helly property. Networks 77(3), 435\u2013453 (2021). https:\/\/doi.org\/10.1002\/net.21998","journal-title":"Networks"},{"issue":"1","key":"1344_CR40","first-page":"33","volume":"24","author":"R Nandakumar","year":"1990","unstructured":"Nandakumar, R., Parthasarathy, K.: Eccentricity-preserving spanning trees. J. Math. Phys. Sci. 24(1), 33\u201335 (1990)","journal-title":"J. Math. Phys. Sci."},{"key":"1344_CR41","doi-asserted-by":"publisher","unstructured":"Manuel Blum, Robert\u00a0W. Floyd, Vaughan\u00a0R. Pratt, Ronald\u00a0L. Rivest, and Robert\u00a0Endre Tarjan. Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973). https:\/\/doi.org\/10.1016\/S0022-0000(73)80033-9","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"1344_CR42","doi-asserted-by":"crossref","unstructured":"Gavoille, Cyril, Peleg, David, Raspaud, Andr\u00e9, Sopena, Eric.: Small k-dominating sets in planar graphs with applications. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pages 201\u2013216. Springer, (2001)","DOI":"10.1007\/3-540-45477-2_19"},{"issue":"4","key":"1344_CR43","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","volume":"1","author":"B Bollob\u00e1s","year":"1980","unstructured":"Bollob\u00e1s, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Comb. 1(4), 311\u2013316 (1980). https:\/\/doi.org\/10.1016\/S0195-6698(80)80030-8","journal-title":"Eur. J. Comb."},{"key":"1344_CR44","doi-asserted-by":"crossref","unstructured":"Gromov, Mikhael.: Hyperbolic groups. In: Gersten, S. (eds) Essays in Group Theory, pp. 75\u2013263. Springer, New York (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"1344_CR45","doi-asserted-by":"publisher","unstructured":"Sean Kennedy, W., Saniee, Iraj, Narayan, Onuttom.: On the hyperbolicity of large-scale networks and its estimation. In James Joshi, George Karypis, Ling Liu, Xiaohua Hu, Ronay Ak, Yinglong Xia, Weijia Xu, Aki-Hiro Sato, Sudarsan Rachuri, Lyle\u00a0H. Ungar, Philip\u00a0S. Yu, Rama Govindaraju, and Toyotaro Suzumura, editors, 2016 IEEE International Conference on Big Data (IEEE BigData 2016), Washington DC, USA, December 5-8, 2016, pages 3344\u20133351. IEEE Computer Society, (2016). https:\/\/doi.org\/10.1109\/BigData.2016.7840994","DOI":"10.1109\/BigData.2016.7840994"},{"key":"1344_CR46","doi-asserted-by":"publisher","unstructured":"Fabien de\u00a0Montgolfier, Mauricio Soto, and Laurent Viennot. Treewidth and hyperbolicity of the internet. In Proceedings of The Tenth IEEE International Symposium on Networking Computing and Applications, NCA 2011, August 25-27, 2011, Cambridge, Massachusetts, USA, pages 25\u201332. IEEE Computer Society, (2011). https:\/\/doi.org\/10.1109\/NCA.2011.11","DOI":"10.1109\/NCA.2011.11"},{"key":"1344_CR47","doi-asserted-by":"publisher","unstructured":"Victor Chepoi and Feodor\u00a0F. Dragan.: A linear-time algorithm for finding a central vertex of a chordal graph. In Jan van Leeuwen, editor, Algorithms - ESA \u201994, Second Annual European Symposium, Utrecht, The Netherlands, September 26-28, 1994, Proceedings, volume 855 of Lecture Notes in Computer Science, pages 159\u2013170. Springer, 1994. URL: https:\/\/doi.org\/10.1007\/BFb0049406","DOI":"10.1007\/BFb0049406"},{"issue":"2\u20133","key":"1344_CR48","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0166-218X(00)00281-X","volume":"113","author":"DG Corneil","year":"2001","unstructured":"Corneil, D.G., Dragan, F.F., Habib, M., Paul, C.: Diameter determination on restricted graph families. Discret. Appl. Math. 113(2\u20133), 143\u2013166 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00281-X","journal-title":"Discret. Appl. Math."},{"key":"1344_CR49","unstructured":"Victor Chepoi. Some $$d$$-convexity properties in triangulated graphs. Math. Res.87, 164\u2013177, (1986). \u015etiin\u0163a, Chi\u015fin\u0103u (Russian)"},{"key":"1344_CR50","doi-asserted-by":"crossref","unstructured":"Victor\u00a0D Chepoi. Centers of triangulated graphs. Mathematical Notes of the Academy of Sciences of the USSR,43:82\u201386, (1988). URL: https:\/\/pageperso.lis-lab.fr\/~victor.chepoi\/centers_triang.pdf","DOI":"10.1007\/BF01139575"},{"key":"1344_CR51","doi-asserted-by":"publisher","unstructured":"Feodor\u00a0F. Dragan, Falk Nicolai, and Andreas Brandst\u00e4dt.: Lexbfs-orderings and power of graphs. In Fabrizio d\u2019Amore, Paolo\u00a0Giulio Franciosa, and Alberto Marchetti-Spaccamela, editors, Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG \u201996, Cadenabbia (Como), Italy, June 12-14, 1996, Proceedings, volume 1197 of Lecture Notes in Computer Science, pages 166\u2013180. Springer, (1996). https:\/\/doi.org\/10.1007\/3-540-62559-3_15","DOI":"10.1007\/3-540-62559-3_15"},{"issue":"3","key":"1344_CR52","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0001-8708(84)90029-X","volume":"53","author":"AWM Dress","year":"1984","unstructured":"Dress, A.W.M.: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Adv. Math. 53(3), 321\u2013402 (1984). https:\/\/doi.org\/10.1016\/0001-8708(84)90029-X","journal-title":"Adv. Math."},{"key":"1344_CR53","doi-asserted-by":"crossref","unstructured":"Isbell, John\u00a0R.: Injective envelopes of banach spaces are rigidly attached. Commentarii mathematici Helvetici,39, 65\u201376, (1964). URL: https:\/\/projecteuclid.org\/journals\/bulletin-of-the-american-mathematical-society\/volume-70\/issue-5\/Injective-envelopes-of-Banach-spaces-are-rigidly-attached\/bams\/1183526270.pdf","DOI":"10.1007\/BF02566944"},{"key":"1344_CR54","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2021.03.022","volume":"867","author":"FF Dragan","year":"2021","unstructured":"Dragan, F.F., Guarnera, H.M.: Helly-gap of a graph and vertex eccentricities. Theor. Comput. Sci. 867, 68\u201384 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.03.022","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1344_CR55","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/s00373-022-02512-z","volume":"38","author":"HM Guarnera","year":"2022","unstructured":"Guarnera, H.M., Dragan, F.F., Leitert, A.: Injective hulls of various graph classes. Graphs Comb. 38(4), 112 (2022). https:\/\/doi.org\/10.1007\/s00373-022-02512-z","journal-title":"Graphs Comb."},{"key":"1344_CR56","doi-asserted-by":"publisher","unstructured":"Feodor\u00a0F. Dragan, Guillaume Ducoffe, and Heather\u00a0M. Guarnera. Fast deterministic algorithms for computing all eccentricities in (hyperbolic) helly graphs. In Anna Lubiw and Mohammad\u00a0R. Salavatipour, editors, Algorithms and Data Structures - 17th International Symposium, WADS 2021, Virtual Event, August 9-11, 2021, Proceedings, volume 12808 of Lecture Notes in Computer Science, pages 300\u2013314. Springer, 2021. https:\/\/doi.org\/10.1007\/978-3-030-83508-8_22","DOI":"10.1007\/978-3-030-83508-8_22"},{"key":"1344_CR57","unstructured":"Feodor\u00a0F. Dragan. Centers of graphs and the Helly property. PhD thesis, Moldova State University, (1989). (in Russian)"},{"key":"1344_CR58","unstructured":"Feodor\u00a0F. Dragan. Conditions for coincidence of local and global minima for eccentricity function on graphs and the helly property. Appl. Math. Inf. Sci. pages 49\u201356, (1990)"},{"key":"1344_CR59","doi-asserted-by":"publisher","unstructured":"Guillaume Ducoffe. Beyond helly graphs: The diameter problem on absolute retracts. In Lukasz Kowalik, Michal Pilipczuk, and Pawel Rzazewski, editors, Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers, volume 12911 of Lecture Notes in Computer Science, pages 321\u2013335. Springer, 2021. https:\/\/doi.org\/10.1007\/978-3-030-86838-3_25","DOI":"10.1007\/978-3-030-86838-3_25"},{"key":"1344_CR60","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113690","volume":"946","author":"G Ducoffe","year":"2023","unstructured":"Ducoffe, G.: Distance problems within helly graphs and k-helly graphs. Theoret. Comput. Sci. 946, 113690 (2023)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1344_CR61","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1002\/jgt.22754","volume":"99","author":"G Ducoffe","year":"2022","unstructured":"Ducoffe, G.: The diameter of at-free graphs. J. Graph Theory 99(4), 594\u2013614 (2022). https:\/\/doi.org\/10.1002\/jgt.22754","journal-title":"J. Graph Theory"},{"key":"1344_CR62","doi-asserted-by":"publisher","unstructured":"David Coudert, Guillaume Ducoffe, and Alexandru Popa.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Trans. Algorithms,15(3), 33:1\u201333:57, (2019). https:\/\/doi.org\/10.1145\/3310228","DOI":"10.1145\/3310228"}],"updated-by":[{"DOI":"10.1007\/s00453-026-01379-3","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T00:00:00Z","timestamp":1775433600000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01344-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01344-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01344-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T09:53:20Z","timestamp":1775469200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01344-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,8]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1344"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01344-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,8]]},"assertion":[{"value":"28 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2026","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised to update section numbers.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2026","order":8,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":9,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00453-026-01379-3","URL":"https:\/\/doi.org\/10.1007\/s00453-026-01379-3","order":11,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"13"}}