{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:28:00Z","timestamp":1778495280238,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T00:00:00Z","timestamp":1559606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T00:00:00Z","timestamp":1559606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00454-019-00107-9","type":"journal-article","created":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T16:08:22Z","timestamp":1559664502000},"page":"856-892","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs"],"prefix":"10.1007","volume":"65","author":[{"given":"J\u00e9r\u00e9mie","family":"Chalopin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0481-7312","authenticated-orcid":false,"given":"Victor","family":"Chepoi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feodor F.","family":"Dragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Ducoffe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdulhakeem","family":"Mohammed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Vax\u00e8s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,4]]},"reference":[{"issue":"1","key":"107_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1002\/net.21631","volume":"67","author":"M Abu-Ata","year":"2016","unstructured":"Abu-Ata, M., Dragan, F.F.: Metric tree-like structures in real-world networks: an empirical study. Networks 67(1), 49\u201368 (2016)","journal-title":"Networks"},{"key":"107_CR2","doi-asserted-by":"crossref","unstructured":"Adcock, A.B., Sullivan, B.D., Mahoney, M.W.: Tree-like structure in large social and information networks. In: Proceedings of the IEEE 13th International Conference on Data Mining. IEEE Computer Society, pp. 1\u201310 (2013)","DOI":"10.1109\/ICDM.2013.77"},{"key":"107_CR3","first-page":"3","volume-title":"Group Theory from a Geometrical Viewpoint","author":"JM Alonso","year":"1991","unstructured":"Alonso, J.M., Brady, T., Cooper, D., Ferlini, V., Lustig, M., Mihalik, M., Shapiro, M., Short, H.: Notes on word hyperbolic groups. In: Ghys, E., Haefliger, A., Verjovsky, A. (eds.) Group Theory from a Geometrical Viewpoint, pp. 3\u201363. World Scientific, River Edge (1991)"},{"key":"107_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-662-48350-3_19","volume-title":"Algorithms\u2014ESA 2015. Lecture Notes in Computer Science","author":"M Borassi","year":"2015","unstructured":"Borassi, M., Coudert, D., Crescenzi, P., Marino, A.: On computing the hyperbolicity of real-world graphs. In: Bansal, N., Finocchi, I. (eds.) Algorithms\u2014ESA 2015. Lecture Notes in Computer Science, vol. 9294, pp. 215\u2013226. Springer, Heidelberg (2015)"},{"key":"107_CR5","first-page":"51","volume-title":"Proceedings of ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science. Electronic Notes in Theoretical Computer Science","author":"M Borassi","year":"2016","unstructured":"Borassi, M., Crescenzi, P., M, Habib: Into the square: on the complexity of some quadratic-time solvable problems. In: Crescenzi, P., Loreti, M. (eds.) Proceedings of ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science. Electronic Notes in Theoretical Computer Science, vol. 322, pp. 51\u201367. Elsevier, Amsterdam (2016)"},{"key":"107_CR6","first-page":"64","volume-title":"Group Theory from a Geometrical Viewpoint","author":"BH Bowditch","year":"1991","unstructured":"Bowditch, B.H.: Notes on Gromov\u2019s hyperbolicity criterion for path-metric spaces. In: Ghys, E., Haefliger, A., Verjovsky, A. (eds.) Group Theory from a Geometrical Viewpoint, pp. 64\u2013167. World Scientific, River Edge (1991)"},{"key":"107_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-Positive Curvature. Grundlehren der mathematischen Wissenschaften","author":"M Bridson","year":"1999","unstructured":"Bridson, M., Haefliger, A.: Metric Spaces of Non-Positive Curvature. Grundlehren der mathematischen Wissenschaften, vol. 319. Springer, Berlin (1999)"},{"issue":"4","key":"107_CR8","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/130941328","volume":"28","author":"J Chalopin","year":"2014","unstructured":"Chalopin, J., Chepoi, V., Papasoglu, P., Pecatte, T.: Cop and robber game and hyperbolicity. SIAM J. Discrete Math. 28(4), 1987\u20132007 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"107_CR9","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Chepoi, V., Dragan, F.F., Ducoffe, G., Mohammed, A., Vax\u00e8s, Y.: Fast approximation and exact computation of negative curvature parameters of graphs. In: Symposium on Computational Geometry, LIPIcs, vol.\u00a099, pp. 22:1\u201322:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern (2018)","DOI":"10.1007\/s00454-019-00107-9"},{"key":"107_CR10","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: Proceedings of the 24th Annual Symposium on Computational Geometry, pp. 59\u201368. ACM, New York (2008)","DOI":"10.1145\/1377676.1377687"},{"issue":"3\u20134","key":"107_CR11","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s00453-010-9478-x","volume":"62","author":"V Chepoi","year":"2012","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for hyperbolic graphs. Algorithmica 62(3\u20134), 713\u2013732 (2012)","journal-title":"Algorithmica"},{"key":"107_CR12","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., Vax\u00e8s, Y.: Core congestion is inherent in hyperbolic networks. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2264\u20132279. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.149"},{"key":"107_CR13","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Estellon, B.: Packing and covering $\\delta $-hyperbolic spaces by balls. In: International Workshop on Approximation Algorithms for Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4627, pp. 59\u201373. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74208-1_5"},{"key":"107_CR14","doi-asserted-by":"publisher","first-page":"1.6:1","DOI":"10.1145\/2780652","volume":"20","author":"N Cohen","year":"2015","unstructured":"Cohen, N., Coudert, D., Lancin, A.: On computing the Gromov hyperbolicity. ACM J. Exp. Algorithmics 20, 1.6:1\u20131.6:18 (2015)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"3","key":"107_CR15","doi-asserted-by":"publisher","first-page":"1601","DOI":"10.1137\/140954787","volume":"28","author":"D Coudert","year":"2014","unstructured":"Coudert, D., Ducoffe, G.: Recognition of $C_4$-free and $1\/2$-hyperbolic graphs. SIAM J. Discrete Math. 28(3), 1601\u20131617 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"107_CR16","doi-asserted-by":"crossref","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2765\u20132784. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.176"},{"issue":"2","key":"107_CR17","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1007\/s00453-017-0291-7","volume":"80","author":"B Das Gupta","year":"2018","unstructured":"Das Gupta, B., Karpinski, M., Mobasheri, N., Yahyanejad, F.: Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications. Algorithmica 80(2), 772\u2013800 (2018)","journal-title":"Algorithmica"},{"issue":"4","key":"107_CR18","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1112\/jtopol\/jtn023","volume":"1","author":"T Delzant","year":"2008","unstructured":"Delzant, T., Gromov, M.: Courbure m\u00e9soscopique et th\u00e9orie de la toute petite simplification. J. Topol. 1(4), 804\u2013836 (2008)","journal-title":"J. Topol."},{"key":"107_CR19","doi-asserted-by":"crossref","unstructured":"Duan, R.: Approximation algorithms for the Gromov hyperbolicity of discrete metric spaces. In: LATIN 2014. Lecture Notes in Computer Science, vol. 8392, pp. 285\u2013293. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-642-54423-1_25"},{"issue":"12","key":"107_CR20","doi-asserted-by":"publisher","first-page":"3889","DOI":"10.1007\/s00453-018-0425-6","volume":"80","author":"K Edwards","year":"2018","unstructured":"Edwards, K., Kennedy, W.S., Saniee, I.: Fast approximation algorithms for $p$-centers in large $\\delta $-hyperbolic graphs. Algorithmica 80(12), 3889\u20133907 (2018)","journal-title":"Algorithmica"},{"key":"107_CR21","doi-asserted-by":"crossref","unstructured":"Fluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R., Talmon, N.: When can graph hyperbolicity be computed in linear time? In: Algorithms and Data Structure. Lecture Notes in Computer Science, vol. 10389, pp. 397\u2013408. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-62127-2_34"},{"issue":"6\u20138","key":"107_CR22","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1016\/j.ipl.2015.02.002","volume":"115","author":"H Fournier","year":"2015","unstructured":"Fournier, H., Ismail, A., Vigneron, A.: Computing the Gromov hyperbolicity of a discrete metric space. Inf. Process. Lett. 115(6\u20138), 576\u2013579 (2015)","journal-title":"Inf. Process. Lett."},{"key":"107_CR23","doi-asserted-by":"crossref","unstructured":"Ghys, \u00c9., de la Harpe, P. (eds.): Les groupes hyperboliques d\u2019apr\u00e8s M. Gromov. Progress in Mathematics, vol. 83. Birkh\u00e4user, Boston (1990)","DOI":"10.1007\/978-1-4684-9167-8"},{"key":"107_CR24","first-page":"75","volume-title":"Essays in Group Theory. Mathematical Sciences Research Institute Publications","author":"M Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8, pp. 75\u2013263. Springer, New York (1987)"},{"issue":"2","key":"107_CR25","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1112\/jtopol\/jtt027","volume":"7","author":"MF Hagen","year":"2014","unstructured":"Hagen, M.F.: Weak hyperbolicity of cube complexes and quasi-arboreal groups. J. Topol. 7(2), 385\u2013418 (2014)","journal-title":"J. Topol."},{"key":"107_CR26","doi-asserted-by":"crossref","unstructured":"Kennedy, W., Saniee, I., Narayan, O.: On the hyperbolicity of large-scale networks and its estimation. In: IEEE International Conference on Big Data, pp. 3344\u20133351. IEEE (2016)","DOI":"10.1109\/BigData.2016.7840994"},{"key":"107_CR27","doi-asserted-by":"publisher","first-page":"066,108","DOI":"10.1103\/PhysRevE.84.066108","volume":"84","author":"O Narayan","year":"2011","unstructured":"Narayan, O., Saniee, I.: Large-scale curvature of networks. Phys. Rev. E 84, 066,108 (2011)","journal-title":"Phys. Rev. E"},{"issue":"2","key":"107_CR28","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF01884301","volume":"121","author":"P Papasoglou","year":"1995","unstructured":"Papasoglou, P.: Strongly geodesically automatic groups are hyperbolic. Invent. Math. 121(2), 323\u2013334 (1995)","journal-title":"Invent. Math."},{"key":"107_CR29","doi-asserted-by":"crossref","unstructured":"Papasoglu, P.: An algorithm detecting hyperbolicity. In: Geometric and Computational Perspectives on Infinite Groups. DIMACS\u2014Series in Discrete Mathematics and Theoretical Computer Science, vol. 25, pp. 193\u2013200. American Mathematical Society, Providence (1996)","DOI":"10.1090\/dimacs\/025\/10"},{"issue":"1\u20133","key":"107_CR30","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0012-365X(99)00142-9","volume":"211","author":"N Polat","year":"2000","unstructured":"Polat, N.: On infinite bridged graphs and strongly dismantlable graphs. Discrete Math. 211(1\u20133), 153\u2013166 (2000)","journal-title":"Discrete Math."},{"issue":"1","key":"107_CR31","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1109\/TNET.2007.899021","volume":"16","author":"Y Shavitt","year":"2008","unstructured":"Shavitt, Y., Tankel, T.: Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE\/ACM Trans. Netw. 16(1), 25\u201336 (2008)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"107_CR32","unstructured":"Soto, M.: Quelques propri\u00e9t\u00e9s topologiques des graphes et applications \u00e0 Internet et aux r\u00e9seaux. Ph.D. thesis, Universit\u00e9 Paris Diderot (2011)"},{"key":"107_CR33","doi-asserted-by":"crossref","unstructured":"Verbeek, K., Suri, S.: Metric embedding, hyperbolic space, and social networks. In: Symposium on Computational Geometry, pp. 501\u2013510. ACM, New York (2014)","DOI":"10.1145\/2582112.2582139"},{"key":"107_CR34","doi-asserted-by":"crossref","unstructured":"Yu, H.: An improved combinatorial algorithm for boolean matrix multiplication. In: Automata, Languages, and Programming. Part I. Lecture Notes in Computer Science, vol. 9134, pp. 1094\u20131105. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-47672-7_89"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00107-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00107-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00107-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,5]],"date-time":"2021-03-05T20:10:42Z","timestamp":1614975042000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00107-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,4]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["107"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00107-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,4]]},"assertion":[{"value":"18 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}