{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T08:34:21Z","timestamp":1748507661672,"version":"3.40.3"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031754081"},{"type":"electronic","value":"9783031754098"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75409-8_31","type":"book-chapter","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:44Z","timestamp":1737497444000},"page":"444-459","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of\u00a0Diameter on\u00a0H-free Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-4419-3143","authenticated-orcid":false,"given":"Jelle J.","family":"Oostveen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5240-7257","authenticated-orcid":false,"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"issue":"1","key":"31_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3563393","volume":"19","author":"A Abboud","year":"2023","unstructured":"Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP, and diameter. ACM Trans. Algorithms 19(1), 1\u201330 (2023)","journal-title":"ACM Trans. Algorithms"},{"key":"31_CR2","unstructured":"Abboud, A., Mozes, S., Weimann, O.: What else can Voronoi diagrams do for diameter in planar graphs? In: Proceedings of ESA 2023. LIPIcs, vol.\u00a0274, pp. 1\u201320. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, R.R., Yu, H.: More applications of the polynomial method to algorithm design. In: Proceedings of SODA 2015, pp. 218\u2013230. SIAM (2015)","DOI":"10.1137\/1.9781611973730.17"},{"key":"31_CR4","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: Proceedings of SODA 2016, pp. 377\u2013391. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Backurs, A., Roditty, L., Segal, G., Williams, V.V., Wein, N.: Towards tight approximation bounds for graph diameter and eccentricities. In: Proceedings of STOC 2018, pp. 267\u2013280. ACM (2018)","DOI":"10.1145\/3188745.3188950"},{"issue":"1\u20133","key":"31_CR6","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","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. Discret. Appl. Math. 82(1\u20133), 43\u201377 (1998)","journal-title":"Discret. Appl. Math."},{"issue":"8","key":"31_CR7","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)","journal-title":"Algorithmica"},{"issue":"2","key":"31_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3218821","volume":"15","author":"S Cabello","year":"2019","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms 15(2), 1\u201338 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"31_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3402926","volume":"17","author":"TM Chan","year":"2021","unstructured":"Chan, T.M., Williams, R.R.: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. ACM Trans. Algorithms 17(1), 1\u201314 (2021)","journal-title":"ACM Trans. Algorithms"},{"key":"31_CR10","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: Proceedings of SODA 2014, pp. 1041\u20131052. SIAM (2014)","DOI":"10.1137\/1.9781611973402.78"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.endm.2008.06.046","volume":"31","author":"V Chepoi","year":"2008","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Notes on diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs. Electron. Notes Discret. Math. 31, 231\u2013234 (2008)","journal-title":"Electron. Notes Discret. Math."},{"issue":"2","key":"31_CR12","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. JGAA 23(2), 393\u2013433 (2019)","journal-title":"JGAA"},{"issue":"2\u20133","key":"31_CR13","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)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"31_CR14","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)","journal-title":"Networks"},{"issue":"3","key":"31_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3310228","volume":"15","author":"D Coudert","year":"2019","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Trans. Algorithms 15(3), 1\u201357 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"31_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2736283","volume":"62","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Gabow, H.N., Sankowski, P.: Algorithmic applications of Baur-Strassen\u2019s theorem: shortest cycles, diameter, and matchings. J. ACM 62(4), 1\u201330 (2015)","journal-title":"J. ACM"},{"key":"31_CR17","unstructured":"Dragan, F.F.: Centers of graphs and the Helly property. Ph. D. Thesis, Moldova State University (1989)"},{"issue":"2","key":"31_CR18","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 1(2), 64\u201383 (1993)","journal-title":"Comput. Sci. J. Moldova"},{"key":"31_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/3-540-58218-5_34","volume-title":"Algorithm Theory \u2014 SWAT \u201994","author":"FF Dragan","year":"1994","unstructured":"Dragan, F.F.: Dominating cliques in distance-hereditary graphs. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol. 824, pp. 370\u2013381. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58218-5_34"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Ducoffe, G.: $$\\alpha _i$$-metric graphs: radius, diameter and all eccentricities. In: Proceedings of WG 2023. LNCS, vol. 14093, pp. 276\u2013290. Springer (2023)","DOI":"10.1007\/978-3-031-43380-1_20"},{"key":"31_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":"31_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":"31_CR23","unstructured":"Dragan, F.F., Habib, M., Viennot, L.: Revisiting radius, diameter, and all eccentricity computation in graphs through certificates. CoRR abs\/1803.04660 (2018)"},{"issue":"3","key":"31_CR24","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0166-218X(99)00157-2","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. Discret. Appl. Math. 98(3), 191\u2013207 (2000)","journal-title":"Discret. Appl. Math."},{"key":"31_CR25","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Nicolai, F., Brandst\u00e4dt, A.: LexBFS-orderings and powers of graphs. In: Proceedings of WG 1996, pp. 166\u2013180. Springer (1997)","DOI":"10.1007\/3-540-62559-3_15"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"Duan, R., Wu, H., Zhou, R.: Faster matrix multiplication via asymmetric hashing. In: Proceedings of FOCS 2023, pp. 2129\u20132138. IEEE (2023)","DOI":"10.1109\/FOCS57990.2023.00130"},{"key":"31_CR27","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"},{"issue":"4","key":"31_CR28","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)","journal-title":"J. Graph Theory"},{"issue":"11","key":"31_CR29","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 centrality computations within bounded clique-width graphs. Algorithmica 84(11), 3192\u20133222 (2022)","journal-title":"Algorithmica"},{"key":"31_CR30","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. Theor. Comput. Sci. 946, 113690 (2023)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"31_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(3), 435\u2013453 (2021)","journal-title":"Networks"},{"key":"31_CR32","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: Proceedings of SODA 2020, pp. 1905\u20131922. SIAM (2020)","DOI":"10.1137\/1.9781611975994.117"},{"key":"31_CR33","unstructured":"Duraj, L., Konieczny, F., Potepa, K.: Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs. CoRR abs\/2307.08162 (2023)"},{"key":"31_CR34","unstructured":"Evald, J., Dahlgaard, S.: Tight hardness results for distance and centrality problems in constant degree graphs. CoRR abs\/1609.08403 (2016)"},{"issue":"3","key":"31_CR35","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0166-218X(80)90039-6","volume":"2","author":"AM Farley","year":"1980","unstructured":"Farley, A.M., Proskurowski, A.: Computation of the center and diameter of outerplanar graphs. Discret. Appl. Math. 2(3), 185\u2013191 (1980)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"31_CR36","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1137\/18M1193402","volume":"50","author":"P Gawrychowski","year":"2021","unstructured":"Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic $${\\tilde{o}}(n^{5\/3})$$ time. SIAM J. Comput. 50(2), 509\u2013554 (2021)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"31_CR37","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"31_CR38","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"31_CR39","unstructured":"Johnson, M., et al.: Complexity framework for forbidden subgraphs. CoRR abs\/2211.12887 (2022)"},{"issue":"3\u20134","key":"31_CR40","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(3\u20134), 121\u2013128 (1990)","journal-title":"Int. J. Comput. Math."},{"key":"31_CR41","unstructured":"Oostveen, J.J., Paulusma, D., van Leeuwen, E.J.: The complexity of diameter on H-free graphs. CoRR abs\/2402.16678 (2024)"},{"key":"31_CR42","doi-asserted-by":"crossref","unstructured":"Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of STOC 2013, pp. 515\u2013524. ACM (2013)","DOI":"10.1145\/2488608.2488673"},{"key":"31_CR43","doi-asserted-by":"crossref","unstructured":"Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: Proceedings of FOCS 1999, pp. 605\u2013615. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814635"},{"issue":"1","key":"31_CR44","doi-asserted-by":"publisher","first-page":"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), 1\u201313 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"31_CR45","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289\u2013317 (2002)","journal-title":"J. ACM"}],"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-75409-8_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:49Z","timestamp":1737497449000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75409-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031754081","9783031754098"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75409-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 January 2025","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":"Gozd Martuljek","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovenia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.famnit.upr.si\/event\/31\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}