{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T11:19:56Z","timestamp":1784373596171,"version":"3.55.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,8,4]],"date-time":"2015-08-04T00:00:00Z","timestamp":1438646400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR project Stint","award":["ANR-13-BS02-0007"],"award-info":[{"award-number":["ANR-13-BS02-0007"]}]},{"name":"European project FP7 EULER","award":["258307"],"award-info":[{"award-number":["258307"]}]},{"name":"ANR program \u201cInvestments for the Future\u201d","award":["ANR-11-LABX-0031-01"],"award-info":[{"award-number":["ANR-11-LABX-0031-01"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,12,15]]},"abstract":"<jats:p>\n            The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best-known theoretical algorithm computing this parameter runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3.69<\/jats:sup>\n            ) time, which is prohibitive for large-scale graphs.\n          <\/jats:p>\n          <jats:p>\n            In this article, we propose an algorithm for determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            ), it is in practice much faster than previous proposals as observed in our experimentations. Finally, we propose a heuristic algorithm that can be used on graphs with millions of nodes. Our algorithms are all evaluated on benchmark instances.\n          <\/jats:p>","DOI":"10.1145\/2780652","type":"journal-article","created":{"date-parts":[[2015,8,7]],"date-time":"2015-08-07T15:27:55Z","timestamp":1438961275000},"page":"1-18","source":"Crossref","is-referenced-by-count":12,"title":["On Computing the Gromov Hyperbolicity"],"prefix":"10.1145","volume":"20","author":[{"given":"Nathann","family":"Cohen","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Sud, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Coudert","sequence":"additional","affiliation":[{"name":"Inria, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aur\u00e9lien","family":"Lancin","sequence":"additional","affiliation":[{"name":"Inria, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,8,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"9th International Workshop on OpenMP (IWOMP)(Lecture Notes in Computer Science)","volume":"8122","author":"Adcock Aaron B.","unstructured":"Aaron B. Adcock , Blair D. Sullivan , Oscar R. Hernandez , and Michael W. Mahoney . 2013. Evaluating OpenMP tasking at scale for the computation of graph hyperbolicity . In 9th International Workshop on OpenMP (IWOMP)(Lecture Notes in Computer Science) , Vol. 8122 . Springer, 71--83. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-40698-0_6 10.1007\/978-3-642-40698-0_6 Aaron B. Adcock, Blair D. Sullivan, Oscar R. Hernandez, and Michael W. Mahoney. 2013. Evaluating OpenMP tasking at scale for the computation of graph hyperbolicity. In 9th International Workshop on OpenMP (IWOMP)(Lecture Notes in Computer Science), Vol. 8122. Springer, 71--83. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-40698-0_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100380902"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3390\/a3020197"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms1063"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-001-8007-7"},{"key":"e_1_2_1_6_1","unstructured":"John Chakerian and Susan Holmes. 2010. distory: Distance Between Phylogenetic Histories. Retrieved from http:\/\/cran.r-project.org\/web\/packages\/distory\/.  John Chakerian and Susan Holmes. 2010. distory: Distance Between Phylogenetic Histories. Retrieved from http:\/\/cran.r-project.org\/web\/packages\/distory\/."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2012.640901"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080052X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.046"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9478-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_13_1","unstructured":"David Coudert. 2014. Gromov Hyperbolicity of Graphs: C Source Code. Retrieved from http:\/\/www-sop.inria.fr\/members\/David.Coudert\/code\/hyperbolicity.shtml.  David Coudert. 2014. Gromov Hyperbolicity of Graphs: C Source Code. Retrieved from http:\/\/www-sop.inria.fr\/members\/David.Coudert\/code\/hyperbolicity.shtml."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/140954787"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603021"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1980-057-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2060100.2060387"},{"key":"e_1_2_1_18_1","volume-title":"Basic Phylogenetic Combinatorics","author":"Dress Andreas","unstructured":"Andreas Dress , Katharina Huber , Jacobus Koolen , Vincent Moulton , and Andreas Spillner . 2011. Basic Phylogenetic Combinatorics . Cambridge University Press , Cambridge, UK . I--XII,1--264 pages. Andreas Dress, Katharina Huber, Jacobus Koolen, Vincent Moulton, and Andreas Spillner. 2011. Basic Phylogenetic Combinatorics. Cambridge University Press, Cambridge, UK. I--XII,1--264 pages."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54423-1_25"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496813"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.02.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"e_1_2_1_23_1","volume-title":"Essays in Group Theory","author":"Gromov Micha","unstructured":"Micha Gromov . 1987. Hyperbolic groups . In Essays in Group Theory , S.M. Gersten (Ed.). Mathematical Sciences Research Institute Publications, Vol . 8. Springer , New York, 75--263. DOI:http:\/\/dx.doi.org\/10.1007\/978-1-4613-9586-7_3 10.1007\/978-1-4613-9586-7_3 Micha Gromov. 1987. Hyperbolic groups. In Essays in Group Theory, S.M. Gersten (Ed.). Mathematical Sciences Research Institute Publications, Vol. 8. Springer, New York, 75--263. DOI:http:\/\/dx.doi.org\/10.1007\/978-1-4613-9586-7_3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.01.001"},{"key":"e_1_2_1_25_1","unstructured":"Luc Hogie and others. 2014. Grph the high performance graph library for Java (Version 1.4.17). The Grph Development Team. Retrieved from http:\/\/grph.inria.fr.  Luc Hogie and others. 2014. Grph the high performance graph library for Java (Version 1.4.17). The Grph Development Team. Retrieved from http:\/\/grph.inria.fr."},{"key":"e_1_2_1_26_1","volume-title":"American Control Conference","volume":"2","author":"Edmond","unstructured":"Edmond A. Jonckheere and Poonsuk Lohsoonthorn. 2004. Geometry of network security . In American Control Conference , Vol. 2 . IEEE, 976--981. Edmond A. Jonckheere and Poonsuk Lohsoonthorn. 2004. Geometry of network security. In American Control Conference, Vol. 2. IEEE, 976--981."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2002.0591"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.036106"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.008"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1455266"},{"key":"e_1_2_1_33_1","volume-title":"The large scale curvature of networks. Physical Review E 84 (Dec","author":"Narayan Onuttom","year":"2011","unstructured":"Onuttom Narayan and Iraj Saniee . 2011. The large scale curvature of networks. Physical Review E 84 (Dec . 2011 ), 066108. DOI:http:\/\/dx.doi.org\/10.1103\/PhysRevE.84.066108 10.1103\/PhysRevE.84.066108 Onuttom Narayan and Iraj Saniee. 2011. The large scale curvature of networks. Physical Review E 84 (Dec. 2011), 066108. DOI:http:\/\/dx.doi.org\/10.1103\/PhysRevE.84.066108"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2014.1002640"},{"key":"e_1_2_1_35_1","unstructured":"Damien Nogu\u00e8s. 2009. \u0394-hyperbolicit\u00e9 et graphes. Master\u2019s thesis. MPRI Universit\u00e9 Paris 7.  Damien Nogu\u00e8s. 2009. \u0394-hyperbolicit\u00e9 et graphes. Master\u2019s thesis. MPRI Universit\u00e9 Paris 7."},{"key":"e_1_2_1_36_1","unstructured":"OpenMP Architecture Review Board. 2008. OpenMP API Version 3.0. Retrieved from http:\/\/www.openmp.org\/.  OpenMP Architecture Review Board. 2008. OpenMP API Version 3.0. Retrieved from http:\/\/www.openmp.org\/."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639562.1639568"},{"key":"e_1_2_1_38_1","volume-title":"R: A Language and Environment for Statistical Computing","author":"Team R Core","year":"2014","unstructured":"R Core Team . 2014 . R: A Language and Environment for Statistical Computing . R Foundation for Statistical Computing, Vienna, Austria . Retrieved from http:\/\/www.r-project.org. R Core Team. 2014. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. Retrieved from http:\/\/www.r-project.org."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492101.1555357"},{"key":"e_1_2_1_40_1","first-page":"27","article-title":"Lack of Gromov-hyperbolicity in colored random networks","volume":"21","author":"Shang Yilun","year":"2011","unstructured":"Yilun Shang . 2011 . Lack of Gromov-hyperbolicity in colored random networks . PanAmerican Mathematical Journal 21 , 1, 27 -- 36 . Yilun Shang. 2011. Lack of Gromov-hyperbolicity in colored random networks. PanAmerican Mathematical Journal 21, 1, 27--36.","journal-title":"PanAmerican Mathematical Journal"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1096536.1096546"},{"key":"e_1_2_1_43_1","volume-title":"Stein and others","author":"William","year":"2014","unstructured":"William A. Stein and others . 2014 . Sage Mathematics Software (Version 6.1). The Sage Development Team . http:\/\/www.sagemath.org. William A. Stein and others. 2014. Sage Mathematics Software (Version 6.1). The Sage Development Team. http:\/\/www.sagemath.org."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90051-2"},{"key":"e_1_2_1_46_1","unstructured":"The Cooperative Association for Internet Data Analysis (CAIDA). 2013. The CAIDA AS Relationships Dataset. Retrieved from http:\/\/www.caida.org\/data\/active\/as-relationships\/.  The Cooperative Association for Internet Data Analysis (CAIDA). 2013. The CAIDA AS Relationships Dataset. Retrieved from http:\/\/www.caida.org\/data\/active\/as-relationships\/."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.37236\/530"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2780652","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2780652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:16Z","timestamp":1750225696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2780652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,4]]},"references-count":44,"alternative-id":["10.1145\/2780652"],"URL":"https:\/\/doi.org\/10.1145\/2780652","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,4]]}}}