{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T02:44:21Z","timestamp":1769741061210,"version":"3.49.0"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2024,3,25]],"date-time":"2024-03-25T00:00:00Z","timestamp":1711324800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,25]],"date-time":"2024-03-25T00:00:00Z","timestamp":1711324800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,7]]},"abstract":"Abstract<\/jats:title>We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called $$\\alpha _i$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric ($$i\\in {\\mathcal {N}}$$<\/jats:tex-math>\n \n i<\/mml:mi>\n \u2208<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) if it satisfies the following $$\\alpha _i$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric property for every vertices u<\/jats:italic>,\u00a0w<\/jats:italic>,\u00a0v<\/jats:italic> and x<\/jats:italic>: if a shortest path between u<\/jats:italic> and w<\/jats:italic> and a shortest path between x<\/jats:italic> and v<\/jats:italic> share a terminal edge vw<\/jats:italic>, then $$d(u,x)\\ge d(u,v) + d(v,x)-i$$<\/jats:tex-math>\n \n d<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n \u2265<\/mml:mo>\n d<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n +<\/mml:mo>\n d<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n ,<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n -<\/mml:mo>\n i<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a \u201cnear-shortest\u201d path with defect at most i<\/jats:italic>. It is known that $$\\alpha _0$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are $$\\alpha _i$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric for $$i=1$$<\/jats:tex-math>\n \n i<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$i=2$$<\/jats:tex-math>\n \n i<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively. We show that an additive O<\/jats:italic>(i<\/jats:italic>)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an $$\\alpha _i$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric graph can be computed in total linear time. Our strongest results are obtained for $$\\alpha _1$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called $$(\\alpha _1,\\varDelta )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n \n \u03b1<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers a question raised in Dragan (Inf Probl Lett 154:105873, 2020), 2020). Our algorithms follow from new results on centers and metric intervals of $$\\alpha _i$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-metric graphs. In particular, we prove that the diameter of the center is at most $$3i+2$$<\/jats:tex-math>\n \n 3<\/mml:mn>\n i<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (at most 3, if $$i=1$$<\/jats:tex-math>\n \n i<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). The latter partly answers a question raised in Yushmanov and Chepoi (Math Probl Cybernet 3:217\u2013232, 1991).<\/jats:p>","DOI":"10.1007\/s00453-024-01223-6","type":"journal-article","created":{"date-parts":[[2024,3,25]],"date-time":"2024-03-25T06:02:11Z","timestamp":1711346531000},"page":"2092-2129","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["$$\\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities"],"prefix":"10.1007","volume":"86","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[]},{"given":"Guillaume","family":"Ducoffe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,25]]},"reference":[{"key":"1223_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Vassilevska Williams, V., Wang, J.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs, In: SODA, pp. 377-391, SIAM, (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"1223_CR2","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, 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"1223_CR3","doi-asserted-by":"crossref","unstructured":"Backurs, A., Roditty, L., Segal, G., Vassilevska Williams, V., Wein, N.: Towards tight approximation bounds for graph diameter and eccentricities. In: STOC, pp. 267\u2013280 (2018)","DOI":"10.1145\/3188745.3188950"},{"key":"1223_CR4","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/S0895480100380902","volume":"16","author":"H-J Bandelt","year":"2003","unstructured":"Bandelt, H.-J., Chepoi, V.: 1-Hyperbolic graphs. SIAM J. Discr. Math. 16, 323\u2013334 (2003)","journal-title":"SIAM J. Discr. Math."},{"key":"1223_CR5","doi-asserted-by":"crossref","unstructured":"Boltyanskii, V. G., Soltan, P. S.: Combinatorial Geometry of Various Classes of Convex Sets [in Russian], S\u0306tiin\u0163a, Kishinev (1978)","DOI":"10.1070\/RM1978v033n01ABEH003730"},{"key":"1223_CR6","first-page":"51","volume":"322","author":"M Borassi","year":"2016","unstructured":"Borassi, M., Crescenzi, P., Habib, M.: Into the square: on the complexity of some quadratic-time solvable problems. Electron. Notes TCS 322, 51\u201367 (2016)","journal-title":"Electron. Notes TCS"},{"key":"1223_CR7","first-page":"43","volume":"82","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings. DAM 82, 43\u201377 (1998)","journal-title":"DAM"},{"key":"1223_CR8","unstructured":"Bringmann, K., Husfeldt, T., Magnusson, M.: Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth. In: IPEC, (2018)"},{"issue":"2","key":"1223_CR9","first-page":"21","volume":"15","author":"S Cabello","year":"2018","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM TALG 15(2), 21 (2018)","journal-title":"ACM TALG"},{"key":"1223_CR10","first-page":"143","volume":"113","author":"D Corneil","year":"2001","unstructured":"Corneil, D., Dragan, F.F., Habib, M., Paul, C.: Diameter determination on restricted graph families. DAM 113, 143\u2013166 (2001)","journal-title":"DAM"},{"key":"1223_CR11","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, 209\u2013222 (2003)","journal-title":"Networks"},{"key":"1223_CR12","doi-asserted-by":"crossref","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs, ACM TALG, 15(3), (2019)","DOI":"10.1145\/3310228"},{"key":"1223_CR13","doi-asserted-by":"crossref","unstructured":"Chechik, S., Larkin, D.H., Roditty, L., Schoenebeck, G., Tarjan, R.E., Vassilevska Williams, V.: Better Approximation Algorithms for the Graph Diameter. In: SODA, pp. 1041\u20131052 (2014)","DOI":"10.1137\/1.9781611973402.78"},{"key":"1223_CR14","unstructured":"Chepoi, V.: Some $$d$$-convexity properties in triangulated graphs. In: Mathematical Research, vol. 87, \u015etiin\u0163a, Chi\u015fin\u0103u, (1986), pp. 164\u2013177 (Russian)"},{"key":"1223_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF01139575","volume":"43","author":"V Chepoi","year":"1988","unstructured":"Chepoi, V.: Centers of triangulated graphs. Math. Notes 43, 143\u2013151 (1988)","journal-title":"Math. Notes"},{"key":"1223_CR16","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F.: A linear-time algorithm for finding a central vertex of a chordal graph. In: Proceedings of the Second European Symposium on Algorithms\u2013ESA\u201994, pp. 159\u2013170","DOI":"10.1007\/BFb0049406"},{"key":"1223_CR17","unstructured":"Chepoi, V., Dragan, F. F.: Disjoint sets problem, (1992)"},{"issue":"1","key":"1223_CR18","first-page":"93","volume":"131","author":"V Chepoi","year":"2003","unstructured":"Chepoi, V., Dragan, F.F.: Finding a central vertex in an HHD-free graph. DAM 131(1), 93\u2013111 (2003)","journal-title":"DAM"},{"key":"1223_CR19","doi-asserted-by":"crossref","unstructured":"Chepoi, V.D., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of $$\\delta $$-hyperbolic geodesic spaces and graphs. In: Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), June 9-11, (2008), College Park, Maryland, USA, pp. 59\u201368","DOI":"10.1145\/1377676.1377687"},{"key":"1223_CR20","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, 393\u2013433 (2019)","journal-title":"J. Graph Algorithms Appl."},{"key":"1223_CR21","unstructured":"Dragan, F. F.: Centers of graphs and the Helly property (in russian), PhD thesis, Moldova State University, Chi\u015fin\u0103u, (1989)"},{"key":"1223_CR22","first-page":"64","volume":"1","author":"FF Dragan","year":"1993","unstructured":"Dragan, F.F.: HT-graphs: centers, connected r-domination and Steiner trees. Comput. Sci. J. Moldova (Kishinev) 1, 64\u201383 (1993)","journal-title":"Comput. Sci. J. Moldova (Kishinev)"},{"key":"1223_CR23","doi-asserted-by":"crossref","unstructured":"Dragan, F.F.: Dominating cliques in distance-hereditary graphs. In: SWAT \u201994, pp. 370\u2013381, Springer, (1994)","DOI":"10.1007\/3-540-58218-5_34"},{"key":"1223_CR24","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0166-218X(99)00077-3","volume":"95","author":"FF Dragan","year":"1999","unstructured":"Dragan, F.F.: Almost diameter of a house-hole-free graph in linear time via LexBFS. Discret. Appl. Math. 95, 223\u2013239 (1999)","journal-title":"Discret. Appl. Math."},{"key":"1223_CR25","doi-asserted-by":"publisher","first-page":"105873","DOI":"10.1016\/j.ipl.2019.105873","volume":"154","author":"FF Dragan","year":"2020","unstructured":"Dragan, F.F.: An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time. Inf. Process. Lett. 154, 105873 (2020)","journal-title":"Inf. Process. Lett."},{"key":"1223_CR26","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-031-43380-1_20","volume":"14093","author":"FF Dragan","year":"2023","unstructured":"Dragan, F.F., Ducoffe, G.: $$\\alpha _i$$-Metric graphs: radius, diameter and all eccentricities. Lect. Notes Comput. Sci. 14093, 276\u2013290 (2023)","journal-title":"Lect. Notes Comput. Sci."},{"key":"1223_CR27","unstructured":"Dragan, F.F., Ducoffe, G.: $$\\alpha _i$$-metric graphs: hyperbolicity. In: Preparation, 2022\u20132023"},{"key":"1223_CR28","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Ducoffe, G., Guarnera, H.M.: Fast deterministic algorithms for computing all eccentricities in (Hyperbolic) Helly Graphs. In: WADS. pp. 300\u2013314 (2021)","DOI":"10.1007\/978-3-030-83508-8_22"},{"key":"1223_CR29","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2020.05.004","volume":"833","author":"FF Dragan","year":"2020","unstructured":"Dragan, F.F., Guarnera, H.M.: Eccentricity function in distance-hereditary graphs. Theor. Comput. Sci. 833, 26\u201340 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1223_CR30","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jcss.2020.03.004","volume":"112","author":"FF Dragan","year":"2020","unstructured":"Dragan, F.F., Guarnera, H.M.: Eccentricity terrain of $$\\delta $$-hyperbolic graphs. J. Comput. Syst. Sci. 112, 50\u201365 (2020)","journal-title":"J. Comput. Syst. Sci."},{"key":"1223_CR31","unstructured":"Dragan, F.F., Habib, M., Viennot, L.: Revisiting radius, diameter, and all eccentricity computation in graphs through certificates, CoRR,arXiv:1803.04660, (2018)"},{"key":"1223_CR32","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.dam.2017.07.017","volume":"232","author":"FF Dragan","year":"2017","unstructured":"Dragan, F.F., K\u00f6hler, E., Alrasheed, H.: Eccentricity approximating trees. Discrete Appl. Math. 232, 142\u2013156 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1223_CR33","first-page":"191","volume":"98","author":"FF Dragan","year":"2000","unstructured":"Dragan, F.F., Nicolai, F.: LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem. DAM 98, 191\u2013207 (2000)","journal-title":"DAM"},{"key":"1223_CR34","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Nicolai, F., Brandst\u00e4dt, A.: LexBFS-orderings and powers of graphs. In: Proceedings of the WG\u201996, Lecture Notes in Computer Science, Vol. 1197, Springer, Berlin, (1997), pp. 166\u2013180","DOI":"10.1007\/3-540-62559-3_15"},{"key":"1223_CR35","first-page":"267","volume":"260","author":"G Ducoffe","year":"2019","unstructured":"Ducoffe, G.: Easy computation of eccentricity approximating trees. DAM 260, 267\u2013271 (2019)","journal-title":"DAM"},{"issue":"4","key":"1223_CR36","first-page":"594","volume":"99","author":"G Ducoffe","year":"2022","unstructured":"Ducoffe, G.: Around the diameter of AT-free graphs. JGT 99(4), 594\u2013614 (2022)","journal-title":"JGT"},{"key":"1223_CR37","doi-asserted-by":"crossref","unstructured":"Ducoffe, G.: Beyond Helly graphs: the diameter problem on absolute retracts. In: WG, pp. 321\u2013335, (2021)","DOI":"10.1007\/978-3-030-86838-3_25"},{"key":"1223_CR38","doi-asserted-by":"publisher","first-page":"3192","DOI":"10.1007\/s00453-022-01015-w","volume":"84","author":"G Ducoffe","year":"2022","unstructured":"Ducoffe, G.: Optimal diameter computation within bounded clique-width graphs. Algorithmica 84, 3192\u20133222 (2022)","journal-title":"Algorithmica"},{"key":"1223_CR39","doi-asserted-by":"publisher","first-page":"113690","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. Theor. Comput. Sci. 946, 113690 (2023)","journal-title":"Theor. Comput. Sci."},{"key":"1223_CR40","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, 435\u2013453 (2021)","journal-title":"Networks"},{"key":"1223_CR41","doi-asserted-by":"crossref","unstructured":"Ducoffe, G., Habib, M., Viennot, L.: Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension, In SODA, pp. 1905- 1922, SIAM, (2020)","DOI":"10.1137\/1.9781611975994.117"},{"key":"1223_CR42","first-page":"185","volume":"2","author":"A Farley","year":"1980","unstructured":"Farley, A., Proskurowski, A.: Computation of the center and diameter of outerplanar graphs. DAM 2, 185\u2013191 (1980)","journal-title":"DAM"},{"key":"1223_CR43","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic $$O(n^{5\/3})$$ time. In: SODA, pp. 495\u2013514, SIAM, (2018)","DOI":"10.1137\/1.9781611975031.33"},{"key":"1223_CR44","first-page":"75","volume-title":"Hyperbolic Groups","author":"M Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic Groups, pp. 75\u2013263. Springer, New York, NY (1987)"},{"key":"1223_CR45","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"28","author":"E Howorka","year":"1977","unstructured":"Howorka, E.: A characterization of distance-hereditary graphs. Quart. J. Math. Oxford Ser. 28, 417\u2013420 (1977)","journal-title":"Quart. J. Math. Oxford Ser."},{"key":"1223_CR46","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-31955-9_3","volume-title":"Network Analysis","author":"D Kosch\u00fctzki","year":"2005","unstructured":"Kosch\u00fctzki, D., Lehmann, K., Peeters, L., Richter, S., Tenfelde-Podehl, D., Zlotowski, O.: Centrality indices. In: Network Analysis, pp. 16\u201361. Springer, Berlin (2005)"},{"key":"1223_CR47","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1080\/00207169008803870","volume":"34","author":"S Olariu","year":"1990","unstructured":"Olariu, S.: A simple linear-time algorithm for computing the center of an interval graph. Int. J. Comput. Math. 34, 121\u2013128 (1990)","journal-title":"Int. J. Comput. Math."},{"key":"1223_CR48","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0012-365X(00)00030-3","volume":"220","author":"E Prisner","year":"2000","unstructured":"Prisner, E.: Eccentricity-approximating trees in chordal graphs. Discrete Math. 220, 263\u2013269 (2000)","journal-title":"Discrete Math."},{"key":"1223_CR49","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: STOC, pp. 515\u2013524. ACM, (2013)","DOI":"10.1145\/2488608.2488673"},{"key":"1223_CR50","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1007\/BF01068561","volume":"19","author":"VP Soltan","year":"1983","unstructured":"Soltan, V.P., Chepoi, V.D.: Conditions for invariance of set diameters under $$d$$-convexification in a graph. Cybernetics 19, 750\u2013756 (1983). (Russian, English transl.)","journal-title":"Cybernetics"},{"issue":"1","key":"1223_CR51","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/2764910","volume":"12","author":"O Weimann","year":"2016","unstructured":"Weimann, O., Yuster, R.: Approximating the diameter of planar graphs in near linear time. ACM Trans. Algorithms 12(1), 12:1-12:13 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"1223_CR52","doi-asserted-by":"publisher","first-page":"43","DOI":"10.37236\/530","volume":"18","author":"Y Wu","year":"2011","unstructured":"Wu, Y., Zhang, C.: Hyperbolicity and chordality of a graph. Electr. J. Comb. 18(1), 43 (2011)","journal-title":"Electr. J. Comb."},{"key":"1223_CR53","first-page":"217","volume":"3","author":"SV Yushmanov","year":"1991","unstructured":"Yushmanov, S.V., Chepoi, V.: A general method of investigation of metric graph properties related to the eccentricity. Math. Probl. Cybernet. 3, 217\u2013232 (1991). (Russian)","journal-title":"Math. Probl. Cybernet."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01223-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01223-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01223-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,17]],"date-time":"2024-07-17T16:03:23Z","timestamp":1721232203000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01223-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,25]]},"references-count":53,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1223"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01223-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,25]]},"assertion":[{"value":"27 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declatration"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}