{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T20:09:37Z","timestamp":1675282177945},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"The diameter of a graph is among its most basic parameters. Since a few years ago, it moreover became a key issue to compute it for massive graphs in the context of complex network analysis. However, known algorithms, including the ones producing approximate values, have too high a time and\/or space complexity to be used in such cases. We propose here a new approach relying on very simple and fast algorithms that compute (upper and lower) bounds for the diameter. We show empirically that, on various real-world cases representative of complex networks studied in the literature, the obtained bounds are very tight (and even equal in some cases). This leads to rigorous and very accurate estimations of the actual diameter in cases which were previously untractable in practice.<\/jats:p>","DOI":"10.1145\/1412228.1455266","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":59,"title":["Fast computation of empirically tight bounds for the diameter of massive graphs"],"prefix":"10.1145","volume":"13","author":[{"given":"Cl\u00e9mence","family":"Magnien","sequence":"first","affiliation":[{"name":"LIP6 -- CNRS and UPMC"}]},{"given":"Matthieu","family":"Latapy","sequence":"additional","affiliation":[{"name":"LIP6 -- CNRS and UPMC"}]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[{"name":"LIAFA -- CNRS and Universit\u00e9 Paris Diderot"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aingworth Chekuri and Motwani. 1996. Fast estimation of diameter and shortest paths (without matrix multiplication). In ACM-SIAM SODA. Aingworth Chekuri and Motwani. 1996. Fast estimation of diameter and shortest paths (without matrix multiplication). In ACM-SIAM SODA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267748"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109614"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the second Annual European Symposium Algorithms, ESA'94","volume":"855","author":"Chepoi V. D.","unstructured":"Chepoi , V. D. and Dragan , F. F . 1994. Linear-time algorithm for finding a central vertex of a chordal graph . In Proceedings of the second Annual European Symposium Algorithms, ESA'94 , LNCS. Vol. 855 . Chepoi, V. D. and Dragan, F. F. 1994. Linear-time algorithm for finding a central vertex of a chordal graph. In Proceedings of the second Annual European Symposium Algorithms, ESA'94, LNCS. Vol. 855."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00281-X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Corneil D. Dragan F. and K\u00f6hler E. 2003. On the power of bfs to determine a graph's diameter. Networks 42 (4). Corneil D. Dragan F. and K\u00f6hler E. 2003. On the power of bfs to determine a graph's diameter. Networks 42 (4).","DOI":"10.1002\/net.10098"},{"key":"e_1_2_1_8_1","first-page":"040","article-title":"All pairs almost shortest paths","volume":"4","author":"Dor D.","year":"1997","unstructured":"Dor , D. , Halperin , S. , and Zwick , U. 1997 . All pairs almost shortest paths . ECCC 4 , 040 . Dor, D., Halperin, S., and Zwick, U. 1997. All pairs almost shortest paths. ECCC 4, 040.","journal-title":"ECCC"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 22nd international workshop. Graph-Theoretic Concepts in Computer Science, WG'96, LNCS.","volume":"1197","author":"Dragan F.","unstructured":"Dragan , F. , Nicolai , F. , and Brandst\u00e4dt , A . 1997. Lexbfs-orderings and powers of graphs . In Proceedings of the 22nd international workshop. Graph-Theoretic Concepts in Computer Science, WG'96, LNCS. Vol. 1197 . Dragan, F., Nicolai, F., and Brandst\u00e4dt, A. 1997. Lexbfs-orderings and powers of graphs. In Proceedings of the 22nd international workshop. Graph-Theoretic Concepts in Computer Science, WG'96, LNCS. Vol. 1197."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1115481.1712333"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103424"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Handler G. 1973. Minimax location of a facility in an undirected tree graph. Transportation Science 7 (3). Handler G. 1973. Minimax location of a facility in an undirected tree graph. Transportation Science 7 (3).","DOI":"10.1287\/trsc.7.3.287"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Latapy M. and Magnien C. 2008. Complex network measurements: Estimating the relevance of observed properties. To appear in the proceedings of ieee infocom. Latapy M. and Magnien C. 2008. Complex network measurements: Estimating the relevance of observed properties. To appear in the proceedings of ieee infocom.","DOI":"10.1109\/INFOCOM.2008.227"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129784"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Watts D. and Strogatz S. 1998. Collective dynamics of small-world networks. Nature 393. Watts D. and Strogatz S. 1998. Collective dynamics of small-world networks. Nature 393.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_19_1","volume-title":"ESA.","author":"Zwick U.","unstructured":"Zwick , U. 2001. Exact and approximate distances in graphs\u2014A survey . In ESA. Vol. 2161 . Zwick, U. 2001. Exact and approximate distances in graphs\u2014A survey. In ESA. Vol. 2161."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1455266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:55:19Z","timestamp":1672304119000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1455266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":19,"alternative-id":["10.1145\/1412228.1455266"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412228.1455266","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2009,2]]}}}