{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T19:29:31Z","timestamp":1770060571972,"version":"3.49.0"},"publisher-location":"Cham","reference-count":74,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030868376","type":"print"},{"value":"9783030868383","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-86838-3_25","type":"book-chapter","created":{"date-parts":[[2021,9,19]],"date-time":"2021-09-19T22:05:30Z","timestamp":1632089130000},"page":"321-335","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Beyond Helly Graphs: The Diameter Problem on Absolute Retracts"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2127-5989","authenticated-orcid":false,"given":"Guillaume","family":"Ducoffe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Vassilevska Williams, V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: SIAM, pp. 377\u2013391 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch28","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Albert, R., Jeong, H., Barab\u00e1si, A.L.: Diameter of the world-wide web. Nature 401(6749), 130\u2013131 (1999)","DOI":"10.1038\/43601"},{"issue":"4","key":"25_CR3","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1002\/jgt.3190080407","volume":"8","author":"HJ Bandelt","year":"1984","unstructured":"Bandelt, H.J.: Retracts of hypercubes. Journal of graph theory 8(4), 501\u2013510 (1984)","journal-title":"Journal of graph theory"},{"key":"25_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1090\/conm\/453\/08795","volume":"453","author":"HJ Bandelt","year":"2008","unstructured":"Bandelt, H.J., Chepoi, V.: Metric graph theory and geometry: a survey. Contem. Math. 453, 49\u201386 (2008)","journal-title":"Contem. Math."},{"issue":"3","key":"25_CR5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0166-218X(87)90058-8","volume":"16","author":"HJ Bandelt","year":"1987","unstructured":"Bandelt, H.J., D\u00e4hlmann, A., Sch\u00fctte, H.: Absolute retracts of bipartite graphs. Discre. Appl. Math. 16(3), 191\u2013215 (1987)","journal-title":"Discre. Appl. Math."},{"issue":"1\u20133","key":"25_CR6","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0166-218X(93)90219-E","volume":"44","author":"HJ Bandelt","year":"1993","unstructured":"Bandelt, H.J., Farber, M., Hell, P.: Absolute reflexive retracts and absolute bipartite retracts. Discre. Appl. Math. 44(1\u20133), 9\u201320 (1993)","journal-title":"Discre. Appl. Math."},{"issue":"3","key":"25_CR7","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0195-6698(89)80053-8","volume":"10","author":"HJ Bandelt","year":"1989","unstructured":"Bandelt, H.J., Pesch, E.: Dismantling absolute retracts of reflexive graphs. Eur. J. Combin. 10(3), 211\u2013220 (1989)","journal-title":"Eur. J. Combin."},{"issue":"1","key":"25_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01197978","volume":"52","author":"H-J Bandelt","year":"1989","unstructured":"Bandelt, H.-J., Pesch, E.: A Radon theorem for Helly graphs. Archiv der Mathematik 52(1), 95\u201398 (1989). https:\/\/doi.org\/10.1007\/BF01197978","journal-title":"Archiv der Mathematik"},{"issue":"1","key":"25_CR9","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0095-8956(91)90051-K","volume":"53","author":"HJ Bandelt","year":"1991","unstructured":"Bandelt, H.J., Pesch, E.: Efficient characterizations of $$n$$-chromatic absolute retracts. J. Combin. Theor. Ser. B 53(1), 5\u201331 (1991)","journal-title":"J. Combin. Theor. Ser. B"},{"issue":"1","key":"25_CR10","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0095-8956(91)90004-4","volume":"51","author":"HJ Bandelt","year":"1991","unstructured":"Bandelt, H.J., Prisner, E.: Clique graphs and Helly graphs. J Combin. Theor. Ser. B 51(1), 34\u201345 (1991)","journal-title":"J Combin. Theor. Ser. B"},{"issue":"3","key":"25_CR11","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM (JACM) 30(3), 479\u2013513 (1983)","journal-title":"J. ACM (JACM)"},{"key":"25_CR12","volume-title":"Graph Theory, Graduate Texts in Mathematics","author":"JA Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory, Graduate Texts in Mathematics, vol. 244. Springer-Verlag, London (2008)"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.entcs.2016.03.005","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. Electr. Notes Theor. Comput. Sci. 322, 51\u201367 (2016)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Borassi, M., Crescenzi, P., Trevisan, L.: An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 920\u2013939. SIAM (2017)","DOI":"10.1137\/1.9781611974782.58"},{"issue":"12","key":"25_CR15","doi-asserted-by":"crossref","first-page":"2302","DOI":"10.1016\/j.disc.2015.05.026","volume":"338","author":"N Bousquet","year":"2015","unstructured":"Bousquet, N., Thomass\u00e9, S.: VC-dimension and Erd\u0151s-P\u00f3sa property. Discre. Math. 338(12), 2302\u20132317 (2015)","journal-title":"Discre. Math."},{"issue":"1","key":"25_CR16","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0166-218X(91)90023-P","volume":"32","author":"A Brandst\u00e4dt","year":"1991","unstructured":"Brandst\u00e4dt, A.: Classes of bipartite graphs related to chordal graphs. Discre. Appl. Math. 32(1), 51\u201360 (1991)","journal-title":"Discre. Appl. Math."},{"issue":"3","key":"25_CR17","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F., Chepoi, V., Voloshin, V.: Dually chordal graphs. SIAM J. Discre. Math. 11(3), 437\u2013455 (1998)","journal-title":"SIAM J. Discre. Math."},{"issue":"8","key":"25_CR18","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":"3","key":"25_CR19","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A characterisation of rigid circuit graphs. Discre. Math. 9(3), 205\u2013212 (1974)","journal-title":"Discre. Math."},{"issue":"2","key":"25_CR20","first-page":"1","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 Tran. Algorith. (TALG) 15(2), 1\u201338 (2018)","journal-title":"ACM Tran. Algorith. (TALG)"},{"key":"25_CR21","unstructured":"Chalopin, J., Chepoi, V., Genevois, A., Hirai, H., Osajda, D.: Helly groups. Tech. Rep. arXiv:2002.06895, arXiv (2020)"},{"issue":"3","key":"25_CR22","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/0605034","volume":"5","author":"G Chang","year":"1984","unstructured":"Chang, G., Nemhauser, G.: The $$k$$-domination and $$k$$-stability problems on sun-free chordal graphs. SIAM J. Algebr. Discre. Methods 5(3), 332\u2013345 (1984)","journal-title":"SIAM J. Algebr. Discre. Methods"},{"issue":"1\u20133","key":"25_CR23","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0012-365X(00)00127-8","volume":"224","author":"M Chastand","year":"2000","unstructured":"Chastand, M., Laviolette, F., Polat, N.: On constructible graphs, infinite bridged graphs and weakly cop-win graphs. Discre. Math. 224(1\u20133), 61\u201378 (2000)","journal-title":"Discre. Math."},{"issue":"6","key":"25_CR24","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1021\/ci9600869","volume":"36","author":"V Chepoi","year":"1996","unstructured":"Chepoi, V.: On distances in benzenoid systems. J. Chem. Inf. Comput. Sci. 36(6), 1169\u20131172 (1996)","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of $$\\delta $$-hyperbolic geodesic spaces and graphs. In: Symposium on Computational Geometry (SocG), pp. 59\u201368. ACM (2008)","DOI":"10.1145\/1377676.1377687"},{"key":"25_CR26","unstructured":"Chepoi, V., Dragan, F., Vax\u00e8s, Y.: Center and diameter problems in plane triangulations and quadrangulations. In: Symposium on Discrete Algorithms (SODA 2002), pp. 346\u2013355 (2002)"},{"key":"25_CR27","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":"2","key":"25_CR28","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s00454-006-1260-0","volume":"37","author":"V Chepoi","year":"2007","unstructured":"Chepoi, V., Estellon, B., Vax\u00e8s, Y.: Covering planar graphs with a fixed number of balls. Discre. Comput. Geom. 37(2), 237\u2013244 (2007)","journal-title":"Discre. Comput. Geom."},{"issue":"2\u20133","key":"25_CR29","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0166-218X(00)00281-X","volume":"113","author":"D Corneil","year":"2001","unstructured":"Corneil, D., Dragan, F., Habib, M., Paul, C.: Diameter determination on restricted graph families. Discre. Appl. Math. 113(2\u20133), 143\u2013166 (2001)","journal-title":"Discre. Appl. Math."},{"issue":"3","key":"25_CR30","doi-asserted-by":"crossref","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. Algorith. (TALG) 15(3), 1\u201357 (2019)","journal-title":"ACM Trans. Algorith. (TALG)"},{"key":"25_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-319-44543-4_29","volume-title":"Combinatorial Algorithms","author":"P Damaschke","year":"2016","unstructured":"Damaschke, P.: Computing giant graph diameters. In: M\u00e4kinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 373\u2013384. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44543-4_29"},{"key":"25_CR32","unstructured":"De Rumeur, J.: Communications dans les r\u00e9seaux de processeurs. Masson, Paris (1994)"},{"key":"25_CR33","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"issue":"1\u20133","key":"25_CR34","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0166-218X(99)00077-3","volume":"95","author":"F Dragan","year":"1999","unstructured":"Dragan, F.: Almost diameter of a house-hole-free graph in linear time via LexBFS. Discr. Appl. Mathe 95(1\u20133), 223\u2013239 (1999)","journal-title":"Discr. Appl. Mathe"},{"key":"25_CR35","unstructured":"Dragan, F.: Centers of graphs and the Helly property. Ph.D. thesis, Moldova State University (1989)"},{"issue":"6","key":"25_CR36","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1007\/BF01122734","volume":"29","author":"F Dragan","year":"1993","unstructured":"Dragan, F.: Domination in quadrangle-free Helly graphs. Cybern. Syst. Anal. 29(6), 822\u2013829 (1993)","journal-title":"Cybern. Syst. Anal."},{"issue":"1\u20133","key":"25_CR37","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0012-365X(95)00277-4","volume":"162","author":"F Dragan","year":"1996","unstructured":"Dragan, F., Brandst\u00e4dt, A.: r-dominating cliques in graphs with hypertree structure. Discre. Math 162(1\u20133), 93\u2013108 (1996)","journal-title":"Discre. Math"},{"issue":"2","key":"25_CR38","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/j.disc.2018.10.017","volume":"342","author":"F Dragan","year":"2019","unstructured":"Dragan, F., Guarnera, H.: Obstructions to a small hyperbolicity in Helly graphs. Discre. Math 342(2), 326\u2013338 (2019)","journal-title":"Discre. Math"},{"key":"25_CR39","doi-asserted-by":"crossref","unstructured":"Dragan, F., Guarnera, H.: Helly-gap of a graph and vertex eccentricities. Tech. Rep. arXiv:2005.01921, arXiv (2020)","DOI":"10.1016\/j.tcs.2021.03.022"},{"issue":"3","key":"25_CR40","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0001-8708(84)90029-X","volume":"53","author":"A Dress","year":"1984","unstructured":"Dress, A.: 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)","journal-title":"Adv. Math"},{"key":"25_CR41","unstructured":"Ducoffe, G.: A new application of orthogonal range searching for computing giant graph diameters. In: Symposium on Simplicity in Algorithms (SOSA) (2019)"},{"key":"25_CR42","unstructured":"Ducoffe, G.: Distance problems within Helly graphs and $$k$$-Helly graphs. Tech. Rep. arXiv:2011.00001, arXiv preprint (2020)"},{"key":"25_CR43","doi-asserted-by":"crossref","unstructured":"Ducoffe, G., Dragan, F.: A story of diameter, radius and Helly property. Networks 77(3), 435\u2013453 (2021)","DOI":"10.1002\/net.21998"},{"key":"25_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-030-36412-0_13","volume-title":"Combinatorial Optimization and Applications","author":"G Ducoffe","year":"2019","unstructured":"Ducoffe, G., Habib, M., Viennot, L.: Fast diameter computation within split\u00a0graphs. In: Li, Y., Cardei, M., Huang, Y. (eds.) COCOA 2019. LNCS, vol. 11949, pp. 155\u2013167. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36412-0_13"},{"key":"25_CR45","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 the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1905\u20131922. SIAM (2020)","DOI":"10.1137\/1.9781611975994.117"},{"issue":"2\u20133","key":"25_CR46","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M Farber","year":"1983","unstructured":"Farber, M.: Characterizations of strongly chordal graphs. Discre. Math. 43(2\u20133), 173\u2013189 (1983)","journal-title":"Discre. Math."},{"issue":"3","key":"25_CR47","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0166-218X(80)90039-6","volume":"2","author":"A Farley","year":"1980","unstructured":"Farley, A., Proskurowski, A.: Computation of the center and diameter of outerplanar graphs. Discre. Appl. Math. 2(3), 185\u2013191 (1980)","journal-title":"Discre. Appl. Math."},{"issue":"1","key":"25_CR48","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"key":"25_CR49","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 $$\\tilde{O}(n^{5\/3})$$ time. In: Symposium on Discrete Algorithms (SODA), pp. 495\u2013514. SIAM (2018)","DOI":"10.1137\/1.9781611975031.33"},{"key":"25_CR50","doi-asserted-by":"crossref","unstructured":"Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"issue":"2","key":"25_CR51","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1002\/jgt.3190020209","volume":"2","author":"M Golumbic","year":"1978","unstructured":"Golumbic, M., Goss, C.: Perfect elimination and chordal bipartite graphs. J. Graph Theor. 2(2), 155\u2013163 (1978)","journal-title":"J. Graph Theor."},{"key":"25_CR52","unstructured":"Guarnera, H., Dragan, F., Leitert, A.: Injective hulls of various graph classes. Tech. Rep. arXiv:2007.14377, arXiv (2020)"},{"key":"25_CR53","unstructured":"Hell, P.: R\u00e9tractions de graphes. Ph.D. thesis, Th\u00e8se (Ph. D.: Math\u00e9matiques)-Universit\u00e9 de Montr\u00e9al. 1972. (1972)"},{"issue":"1","key":"25_CR54","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0095-8956(74)90040-9","volume":"17","author":"P Hell","year":"1974","unstructured":"Hell, P.: Absolute planar retracts and the four color conjecture. J. Combin. Theor, Ser. B 17(1), 5\u201310 (1974)","journal-title":"J. Combin. Theor, Ser. B"},{"issue":"3","key":"25_CR55","doi-asserted-by":"crossref","first-page":"544","DOI":"10.4153\/CJM-1987-025-1","volume":"39","author":"P Hell","year":"1987","unstructured":"Hell, P., Rival, I.: Absolute retracts and varieties of reflexive graphs. Canadian journal of mathematics 39(3), 544\u2013567 (1987)","journal-title":"Canadian journal of mathematics"},{"key":"25_CR56","doi-asserted-by":"publisher","unstructured":"Hell, P.: Absolute retracts in graphs. In: In: Bari R.A., Harary, F. (eds.) Graphs and Combinatorics. Lecture Notes in Mathematics, vol. 406, pp. 291\u2013301 (1974). Springer, Berlin (1974). https:\/\/doi.org\/10.1007\/BFb0066450","DOI":"10.1007\/BFb0066450"},{"issue":"1","key":"25_CR57","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF02566944","volume":"39","author":"J Isbell","year":"1964","unstructured":"Isbell, J.: Six theorems about injective metric spaces. Commentarii Mathematici Helvetici 39(1), 65\u201376 (1964)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"25_CR58","unstructured":"Johnson, D.S., Garey, M.R.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman, San Francisco (1979)"},{"issue":"1\u20133","key":"25_CR59","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0012-365X(93)E0062-9","volume":"134","author":"S Klav\u017ear","year":"1994","unstructured":"Klav\u017ear, S.: Absolute retracts of split graphs. Discre. Math 134(1\u20133), 75\u201384 (1994)","journal-title":"Discre. Math"},{"key":"25_CR60","doi-asserted-by":"crossref","unstructured":"Klisowski, J.: A survey of various modifications of the notions of absolute retracts and absolute neighborhood retracts. In: Colloquium Mathematicum, vol. 46, pp. 23\u201335. Institute of Mathematics Polish Academy of Sciences (1982)","DOI":"10.4064\/cm-46-1-23-35"},{"issue":"3","key":"25_CR61","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s11590-017-1126-9","volume":"12","author":"T Kloks","year":"2017","unstructured":"Kloks, T., Wang, Y.-L.: On retracts, absolute retracts, and foldings in cographs. Optim. Lett. 12(3), 535\u2013549 (2017). https:\/\/doi.org\/10.1007\/s11590-017-1126-9","journal-title":"Optim. Lett."},{"issue":"11","key":"25_CR62","doi-asserted-by":"crossref","first-page":"4258","DOI":"10.1007\/s00453-018-0440-7","volume":"81","author":"HO Le","year":"2019","unstructured":"Le, H.O., Le, V.: Hardness and structural results for half-squares of restricted tree convex bipartite graphs. Algorithmica 81(11), 4258\u20134274 (2019)","journal-title":"Algorithmica"},{"issue":"1","key":"25_CR63","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.ipl.2007.02.017","volume":"103","author":"M Lin","year":"2007","unstructured":"Lin, M., Szwarcfiter, J.: Faster recognition of clique-Helly and hereditary clique-Helly graphs. Inf. Process. Lett. 103(1), 40\u201343 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"10\u201311","key":"25_CR64","doi-asserted-by":"crossref","first-page":"1507","DOI":"10.1016\/j.disc.2009.08.013","volume":"310","author":"C Loten","year":"2010","unstructured":"Loten, C.: Absolute retracts and varieties generated by chordal graphs. Discre Math. 310(10\u201311), 1507\u20131519 (2010)","journal-title":"Discre Math."},{"issue":"3\u20134","key":"25_CR65","doi-asserted-by":"crossref","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."},{"issue":"4","key":"25_CR66","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1002\/jgt.3190110416","volume":"11","author":"E Pesch","year":"1987","unstructured":"Pesch, E.: Minimal extensions of graphs to absolute retracts. J. Graph Theor. 11(4), 585\u2013598 (1987)","journal-title":"J. Graph Theor."},{"key":"25_CR67","doi-asserted-by":"crossref","unstructured":"Pesch, E.: Products of absolute retracts. Discre. Math. 69(2), 179\u2013188 (1988)","DOI":"10.1016\/0012-365X(88)90016-7"},{"issue":"1\u20132","key":"25_CR68","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0012-365X(85)90159-1","volume":"57","author":"E Pesch","year":"1985","unstructured":"Pesch, E., Poguntke, W.: A characterization of absolute retracts of $$n$$-chromatic graphs. Discre. Math. 57(1\u20132), 99\u2013104 (1985)","journal-title":"Discre. Math."},{"issue":"1\u20133","key":"25_CR69","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0012-365X(00)00210-7","volume":"229","author":"N Polat","year":"2001","unstructured":"Polat, N.: Convexity and fixed-point properties in Helly graphs. Discre. Math. 229(1\u20133), 197\u2013211 (2001)","journal-title":"Discre. Math."},{"issue":"4","key":"25_CR70","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1002\/jgt.10120","volume":"43","author":"N Polat","year":"2003","unstructured":"Polat, N.: On constructible graphs, locally Helly graphs, and convexity. J. Graph Theor. 43(4), 280\u2013298 (2003)","journal-title":"J. Graph Theor."},{"key":"25_CR71","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC), pp. 515\u2013524 (2013)","DOI":"10.1145\/2488608.2488673"},{"issue":"3","key":"25_CR72","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R Tarjan","year":"1984","unstructured":"Tarjan, R., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Computi. 13(3), 566\u2013579 (1984)","journal-title":"SIAM J. Computi."},{"key":"25_CR73","unstructured":"Walter, J.R.: Representations of rigid cycle graphs. Ph.D. thesis, Wayne State University, Department of Mathematics (1972)"},{"issue":"6684","key":"25_CR74","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D Watts","year":"1998","unstructured":"Watts, D., Strogatz, S.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"}],"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-030-86838-3_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T20:03:49Z","timestamp":1702065829000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86838-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030868376","9783030868383"],"references-count":74,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86838-3_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 September 2021","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":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 June 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"47","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair and OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held online due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}