{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:56:19Z","timestamp":1772121379781,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642308499","type":"print"},{"value":"9783642308505","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30850-5_10","type":"book-chapter","created":{"date-parts":[[2012,5,28]],"date-time":"2012-05-28T01:44:33Z","timestamp":1338169473000},"page":"99-110","source":"Crossref","is-referenced-by-count":20,"title":["On Computing the Diameter of Real-World Directed (Weighted) Graphs"],"prefix":"10.1007","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[]},{"given":"Leonardo","family":"Lanzi","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Boldi, P., Rosa, M., Ugander, J., Vigna, S.: Four Degrees of Separation (2011) arXiv:1111.4570v1","DOI":"10.1145\/2380718.2380723"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, S., Khandelwal, S., Meyers, L.: Exploring biological network structure with clustered random networks. BMC Bioinformatics 10(1), 405+ (2009)","DOI":"10.1186\/1471-2105-10-405"},{"key":"10_CR3","first-page":"595","volume-title":"Proceedings of the 13th International World Wide Web Conference","author":"P. Boldi","year":"2003","unstructured":"Boldi, P., Vigna, S.: The WebGraph Framework I: Compression Techniques. In: Proceedings of the 13th International World Wide Web Conference, pp. 595\u2013601. ACM Press, Manhattan (2003)"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., Vigna, S.: Hyperanf: approximating the neighbourhood function of very large graphs on a budget. In: WWW, pp. 625\u2013634 (2011)","DOI":"10.1145\/1963405.1963493"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Brandes, U., Erlebach, T.: Network Analysis: Methodological Foundations. Springer (2005)","DOI":"10.1007\/b106453"},{"issue":"1-6","key":"10_CR6","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S1389-1286(00)00083-9","volume":"33","author":"A.Z. Broder","year":"2000","unstructured":"Broder, A.Z., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.L.: Graph structure in the web. Computer Networks\u00a033(1-6), 309\u2013320 (2000)","journal-title":"Computer Networks"},{"key":"10_CR7","unstructured":"9th DIMACS Implementation Challenge - Shortest Paths (2006), http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/1377676.1377687","volume-title":"Proceedings of the 24th Annual Symposium on Computational Geometry, SCG 2008","author":"V. Chepoi","year":"2008","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, SCG 2008, pp. 59\u201368. ACM, New York (2008)"},{"key":"10_CR9","unstructured":"Crescenzi, P., Grossi, R., Habib, M., Lanzi, L., Marino, A.: On Computing the Diameter of Real-World Undirected Graphs. Presented at Workshop on Graph Algorithms and Applications (Zurich\u2013July 3, 2011) and selected for submission to the special issue of Theoretical Computer Science in honor of Giorgio Ausiello in the occasion of his 70th birthday (2011)"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/978-3-642-15775-2_26","volume-title":"Algorithms \u2013 ESA 2010","author":"P. Crescenzi","year":"2010","unstructured":"Crescenzi, P., Grossi, R., Imbrenda, C., Lanzi, L., Marino, A.: Finding the Diameter in Real-World Graphs. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 302\u2013313. Springer, Heidelberg (2010)"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. Dijkstra","year":"1959","unstructured":"Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"10_CR12","volume-title":"Complex Networks: Structure, Robustness and Function","author":"S. Havlin","year":"2010","unstructured":"Havlin, S., Cohen, R.: Complex Networks: Structure, Robustness and Function. Cambridge University Press, Cambridge (2010)"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Junker, B.O.H., Schreiber, F.: Analysis of Biological Networks. Wiley Series in Bioinformatics. Wiley Interscience (2008)","DOI":"10.1002\/9780470253489"},{"issue":"2","key":"10_CR14","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/1921632.1921634","volume":"5","author":"U. Kang","year":"2011","unstructured":"Kang, U., Tsourakakis, C.E., Appel, A.P., Faloutsos, C., Leskovec, J.: Hadi: Mining radii of large graphs. TKDD\u00a05(2), 8 (2011)","journal-title":"TKDD"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Kang, U., Tsourakakis, C.E., Faloutsos, C.: PEGASUS: A Peta-Scale graph mining system implementation and observations. In: 2009 Ninth IEEE International Conference on Data Mining, pp. 229\u2013238. IEEE (December 2009)","DOI":"10.1109\/ICDM.2009.14"},{"key":"10_CR16","unstructured":"Latapy, M., Magnien, C.: Measuring Fundamental Properties of Real-World Complex Networks. CoRR abs\/cs\/0609115 (2006)"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1145\/1150402.1150479","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2006","author":"J. Leskovec","year":"2006","unstructured":"Leskovec, J., Faloutsos, C.: Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2006, pp. 631\u2013636. ACM, New York (2006)"},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J. Leskovec","year":"2009","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics\u00a06(1), 29\u2013123 (2009)","journal-title":"Internet Mathematics"},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/3-540-45749-6_63","volume-title":"Algorithms - ESA 2002","author":"K. Mehlhorn","year":"2002","unstructured":"Mehlhorn, K., Meyer, U.: External-Memory Breadth-First Search with Sublinear I\/O. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 723\u2013735. Springer, Heidelberg (2002)"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1298306.1298311","volume-title":"Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, IMC 2007","author":"A. Mislove","year":"2007","unstructured":"Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, IMC 2007, pp. 29\u201342. ACM, New York (2007)"},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"M.E.J. Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Review\u00a045, 167\u2013256 (2003)","journal-title":"SIAM Review"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Palmer, C.R., Gibbons, P.B., Faloutsos, C.: ANF: a Fast and Scalable Tool for Data Mining in Massive Graphs. In: Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 81\u201390 (2002)","DOI":"10.1145\/775047.775059"},{"key":"10_CR23","unstructured":"SNAP: Stanford Network Analysis Package (SNAP) (2009), http:\/\/snap.stanford.edu"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Takes, F.W., Kosters, W.A.: Determining the diameter of small world networks. In: CIKM, pp. 1191\u20131196 (2011)","DOI":"10.1145\/2063576.2063748"},{"key":"10_CR25","unstructured":"Network datasets (2009), http:\/\/toreopsahl.com\/datasets\/"},{"key":"10_CR26","doi-asserted-by":"crossref","first-page":"036123","DOI":"10.1103\/PhysRevE.73.036123","volume":"73","author":"F. Wang","year":"2006","unstructured":"Wang, F., Moreno, Y., Sun, Y.: Structure of peer-to-peer social networks. Phys. Rev. E\u00a073, 036123 (2006)","journal-title":"Phys. Rev. E"},{"key":"10_CR27","unstructured":"WebGraph: WebGraph (2001), http:\/\/webgraph.dsi.unimi.it\/"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30850-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T22:44:11Z","timestamp":1743201851000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30850-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308499","9783642308505"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30850-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}