{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T11:49:49Z","timestamp":1751456989197,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031433795"},{"type":"electronic","value":"9783031433801"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43380-1_20","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"276-290","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["$$\\alpha _i$$-Metric Graphs: Radius, Diameter and\u00a0all Eccentricities"],"prefix":"10.1007","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Ducoffe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"key":"20_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\u2013391. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"20_CR2","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 2018, pp. 267\u2013280 (2018)","DOI":"10.1145\/3188745.3188950"},{"key":"20_CR3","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":"20_CR4","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":"20_CR5","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":"20_CR6","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":"20_CR7","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":"20_CR8","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":"20_CR9","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 2014, pp. 1041\u20131052 (2014)","DOI":"10.1137\/1.9781611973402.78"},{"key":"20_CR10","unstructured":"Chepoi, V.: Some $$d$$-convexity properties in triangulated graphs. In: Mathematical Research, vol. 87, pp. 164\u2013177. \u015etiin\u0163a, Chi\u015fin\u0103u (1986). (Russian)"},{"key":"20_CR11","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":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BFb0049406","volume-title":"Algorithms \u2014 ESA \u201994","author":"V Chepoi","year":"1994","unstructured":"Chepoi, V., Dragan, F.: A linear-time algorithm for finding a central vertex of a chordal graph. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 159\u2013170. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0049406"},{"issue":"1","key":"20_CR13","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":"20_CR14","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), 9\u201311 June 2008, College Park, Maryland, USA, pp. 59\u201368 (2008)","DOI":"10.1145\/1377676.1377687"},{"key":"20_CR15","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":"20_CR16","unstructured":"Dragan, F.F.: Centers of graphs and the Helly property (in Russian). Ph.D. thesis, Moldava State University, Chi\u015fin\u0103u (1989)"},{"key":"20_CR17","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":"20_CR18","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":"20_CR19","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Ducoffe, G.: $$\\alpha _i$$-metric graphs: radius, diameter and all eccentricities. CoRR, abs\/2305.02545 (2023)","DOI":"10.1007\/978-3-031-43380-1_20"},{"key":"20_CR20","unstructured":"Dragan, F.F., Ducoffe, G.: $$\\alpha _i$$-metric graphs: hyperbolicity. In: Preparation (2022\u20132023)"},{"key":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/978-3-030-83508-8_22","volume-title":"Algorithms and Data Structures","author":"FF Dragan","year":"2021","unstructured":"Dragan, F.F., Ducoffe, G., Guarnera, H.M.: Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs. In: Lubiw, A., Salavatipour, M. (eds.) WADS 2021. LNCS, vol. 12808, pp. 300\u2013314. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-83508-8_22"},{"key":"20_CR22","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":"20_CR23","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":"20_CR24","unstructured":"Dragan, F.F., Habib, M., Viennot, L.: Revisiting radius, diameter, and all eccentricity computation in graphs through certificates. CoRR, abs\/1803.04660 (2018)"},{"key":"20_CR25","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. Discret. Appl. Math. 232, 142\u2013156 (2017)","journal-title":"Discret. Appl. Math."},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/3-540-62559-3_15","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"FF Dragan","year":"1997","unstructured":"Dragan, F.F., Nicolai, F., Brandst\u00e4dt, A.: LexBFS-orderings and powers of graphs. In: d\u2019Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) WG 1996. LNCS, vol. 1197, pp. 166\u2013180. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-62559-3_15"},{"key":"20_CR27","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":"20_CR28","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":"20_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-030-86838-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"G Ducoffe","year":"2021","unstructured":"Ducoffe, G.: Beyond Helly graphs: the diameter problem on absolute retracts. In: Kowalik, \u0141, Pilipczuk, M., Rz\u0105\u017cewski, P. (eds.) WG 2021. LNCS, vol. 12911, pp. 321\u2013335. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_25"},{"key":"20_CR30","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":"20_CR31","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":"20_CR32","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":"20_CR33","series-title":"Lecture Notes in Computer Science","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.A., Peeters, L., Richter, S., Tenfelde-Podehl, D., Zlotowski, O.: Centrality indices. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 16\u201361. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-31955-9_3"},{"key":"20_CR34","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":"20_CR35","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. Discret. Math. 220, 263\u2013269 (2000)","journal-title":"Discret. Math."},{"key":"20_CR36","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":"20_CR37","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"},{"key":"20_CR38","doi-asserted-by":"crossref","unstructured":"Weimann, O., Yuster, R.: Approximating the diameter of planar graphs in near linear time. ACM Trans. Algorithms 12(1), 12:1\u201312:13 (2016)","DOI":"10.1145\/2764910"},{"key":"20_CR39","unstructured":"Yushmanov, S.V., Chepoi, V.: A general method of investigation of metric graph properties related to the eccentricity. In: Mathematical Problems in Cybernetics, vol. 3, pp. 217\u2013232. Nauka, Moscow (1991). (Russian)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43380-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T11:58:12Z","timestamp":1703246292000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}