{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:56:20Z","timestamp":1772121380251,"version":"3.50.1"},"reference-count":36,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Project 20174LF3T8"],"award-info":[{"award-number":["PRIN Project 20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["L. 232 (Dipartimenti di Eccellenza)"],"award-info":[{"award-number":["L. 232 (Dipartimenti di Eccellenza)"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"publisher","award":["SID 2020: Resource-Allocation Tradeoffs for Dynamic and Extreme Data"],"award-info":[{"award-number":["SID 2020: Resource-Allocation Tradeoffs for Dynamic and Extreme Data"]}],"id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1740741"],"award-info":[{"award-number":["CCF 1740741"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS 1813444"],"award-info":[{"award-number":["IIS 1813444"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art \u0394-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio.<\/jats:p>","DOI":"10.3390\/a13090216","type":"journal-article","created":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T14:21:10Z","timestamp":1598970070000},"page":"216","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Distributed Graph Diameter Approximation"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2783-0218","authenticated-orcid":false,"given":"Matteo","family":"Ceccarello","sequence":"first","affiliation":[{"name":"Faculty of Computer Science, Free University of Bozen, 39100 Bolzano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Pietracaprina","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, University of Padova, 35131 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9189-6938","authenticated-orcid":false,"given":"Geppino","family":"Pucci","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, University of Padova, 35131 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9321-9460","authenticated-orcid":false,"given":"Eli","family":"Upfal","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Brown University, Providence, RI 02912, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,1]]},"reference":[{"key":"ref_1","unstructured":"Barabasi, A.L. (2016). Network Science, Cambridge University Press."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Roditty, L., and Williams, V.V. (2013, January 1\u20134). Fast approximation algorithms for the diameter and radius of sparse graphs. Proceedings of the Symposium on Theory of Computing, Palo Alto, CA, USA.","DOI":"10.1145\/2488608.2488673"},{"key":"ref_3","unstructured":"Pettie, S., and Ramachandran, V. (2002, January 6\u20138). Computing Shortest Paths with Comparisons and Additions. Proceedings of the Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Williams, V.V. (2012, January 19\u201322). Multiplying matrices faster than Coppersmith-Winograd. Proceedings of the Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/2213977.2214056"},{"key":"ref_5","unstructured":"Aho, A.V., Hopcroft, J.E., and Ullman, J.D. (1974). The Design and Analysis of Computer Algorithms, Addison-Wesley."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/1412228.1455266","article-title":"Fast computation of empirically tight bounds for the diameter of massive graphs","volume":"13","author":"Magnien","year":"2009","journal-title":"J. Exp. Algorithmics"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.tcs.2012.09.018","article-title":"On computing the diameter of real-world undirected graphs","volume":"514","author":"Crescenzi","year":"2013","journal-title":"Theory Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Grossi, R., Lanzi, L., and Marino, A. (2012, January 7\u20139). On Computing the Diameter of Real-World Directed (Weighted) Graphs. Proceedings of the Symposium on Experimental Algorithms, Bordeaux, France.","DOI":"10.1007\/978-3-642-30850-5_10"},{"key":"ref_9","unstructured":"Faloutsos, M., Faloutsos, P., and Faloutsos, C. (September, January 30). On Power-law Relationships of the Internet Topology. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Stockholm, Sweden."},{"key":"ref_10","unstructured":"Palmer, C.R., Gibbons, P.B., and Faloutsos, C. (2002, January 23\u201326). ANF: A Fast and Scalable Tool for Data Mining in Massive Graphs. Proceedings of the International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, Canada."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Flajolet, P., and Martin, G. (1983, January 7\u20139). Probabilistic Counting. Proceedings of the Symposium on Foundations of Computer Science, Tucson, AZ, USA.","DOI":"10.1109\/SFCS.1983.46"},{"key":"ref_12","unstructured":"Boldi, P., Rosa, M., and Vigna, S. (April, January 28). HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget. Proceedings of the International Conference on World Wide Web, Hyderabad, India."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Fusy, \u00c9., Gandouet, O., and Meunier, F. (2007, January 17\u201322). HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm. Proceedings of the 2007 Conference on Analysis of Algorithms (AofA\u201907), Juan des Pins, France.","DOI":"10.46298\/dmtcs.3545"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Boldi, P., and Vigna, S. (2013, January 7\u201310). In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond. Proceedings of the Workshop of the International Conference on Data Mining, Dallas, TX, USA.","DOI":"10.1109\/ICDMW.2013.10"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"8:1","DOI":"10.1145\/1921632.1921634","article-title":"HADI: Mining Radii of Large Graphs","volume":"5","author":"Kang","year":"2011","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Meyer, U. (2008, January 2\u20134). On Trade-Offs in External-Memory Diameter-Approximation. Proceedings of the Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden.","DOI":"10.1007\/978-3-540-69903-3_38"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Peng, R., and Xu, S.C. (2013, January 23\u201325). Parallel graph decompositions using random shifts. Proceedings of the Symposium on Parallelism in Algorithms and Architectures, Montreal, QC, Canada.","DOI":"10.1145\/2486159.2486180"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Shun, J., Dhulipala, L., and Blelloch, G.E. (2014, January 23\u201325). A simple and practical linear-work parallel algorithm for connectivity. Proceedings of the Symposium on Parallelism in Algorithms and Architectures, Prague, Czech Republic.","DOI":"10.1145\/2612669.2612692"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1145\/331605.331610","article-title":"Polylog-time and near-linear work approximation scheme for undirected shortest paths","volume":"47","author":"Cohen","year":"2000","journal-title":"J. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/S0196-6774(03)00076-2","article-title":"\u0394-stepping: A parallelizable shortest path algorithm","volume":"49","author":"Meyer","year":"2003","journal-title":"J. Algorithms"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Pietracaprina, A., Pucci, G., and Upfal, E. (2015, January 13\u201315). Space and Time Efficient Parallel Graph Decomposition, Clustering, and Diameter Approximation. Proceedings of the Symposium on Parallelism in Algorithms and Architectures, Portland, OR, USA.","DOI":"10.1145\/2755573.2755591"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Pietracaprina, A., Pucci, G., and Upfal, E. (2016, January 23\u201327). A Practical Parallel Algorithm for Diameter Approximation of Massive Weighted Graphs. Proceedings of the International Parallel and Distributed Processing Symposium, Chicago, IL, USA.","DOI":"10.1109\/IPDPS.2016.61"},{"key":"ref_23","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., and Malkhi, D. (2006, January 4\u20137). Routing in Networks with Low Doubling Dimension. Proceedings of the International Conference on Distributed Computing Systems, Lisboa, Portugal."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Murray, D.G., McSherry, F., Isaacs, R., Isard, M., Barham, P., and Abadi, M. (2013, January 3\u20136). Naiad: A Timely Dataflow System. Proceedings of the Symposium on Operating Systems Principles, Farmington, PA, USA.","DOI":"10.1145\/2517349.2522738"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"766","DOI":"10.14778\/3317315.3317319","article-title":"Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially","volume":"12","author":"Ceccarello","year":"2019","journal-title":"Proc. VLDB Endow."},{"key":"ref_26","unstructured":"Mazzetto, A., Pietracaprina, A., and Pucci, G. (2019, January 8\u201311). Accurate MapReduce Algorithms for k-Median and k-Means in General Metric Spaces. Proceedings of the International Symposium on Algorithms and Computation, Shanghai, China."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"469","DOI":"10.14778\/3055540.3055541","article-title":"MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension","volume":"10","author":"Ceccarello","year":"2017","journal-title":"Proc. VLDB Endow."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Pietracaprina, A., and Pucci, G. (2018, January 5\u20139). Fast Coreset-based Diversity Maximization under Matroid Constraints. Proceedings of the International Conference on Web Search and Data Mining, Marina Del Rey, CA, USA.","DOI":"10.1145\/3159652.3159719"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","article-title":"MapReduce: Simplified data processing on large clusters","volume":"51","author":"Dean","year":"2008","journal-title":"Commun. ACM"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Pietracaprina, A., Pucci, G., Riondato, M., Silvestri, F., and Upfal, E. (2012, January 25\u201329). Space-round tradeoffs for MapReduce computations. Proceedings of the International Conference on Supercomputing, Venice, Italy.","DOI":"10.1145\/2304576.2304607"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., and Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1112\/blms\/7.3.225","article-title":"The genealogy of genealogy branching processes before (and after) 1873","volume":"7","author":"Kendall","year":"1975","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Van Der Hofstad, R. (2016). Random Graphs and Complex Networks, Cambridge University Press.","DOI":"10.1017\/9781316779422"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"682","DOI":"10.2307\/3212112","article-title":"The total progeny in a branching process and a related random walk","volume":"6","author":"Dwass","year":"1969","journal-title":"J. Appl. Probab."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Boldi, P., and Vigna, S. (2004, January 17\u201320). The WebGraph Framework I: Compression Techniques. Proceedings of the International Conference on World Wide Web, New York, NY, USA.","DOI":"10.1145\/988672.988752"},{"key":"ref_36","unstructured":"Boldi, P., Rosa, M., Santini, M., and Vigna, S. (\u20131, January 28). Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks. Proceedings of the International Conference on World Wide Web, Hyderabad, India."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/216\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:05:39Z","timestamp":1760177139000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,1]]},"references-count":36,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090216"],"URL":"https:\/\/doi.org\/10.3390\/a13090216","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,1]]}}}