{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T10:30:47Z","timestamp":1770546647644,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1527867,CCF-1540512,IIS-1633720,CCF-1717075"],"award-info":[{"award-number":["CCF-1527867,CCF-1540512,IIS-1633720,CCF-1717075"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"US-Israel Binational Science Foundation","award":["2016419"],"award-info":[{"award-number":["2016419"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,1,4]]},"DOI":"10.1145\/3491003.3491011","type":"proceedings-article","created":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T00:14:42Z","timestamp":1643069682000},"page":"40-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Distributed Algorithms for Connectivity and MST in Large Graphs with Efficient Local Computation"],"prefix":"10.1145","author":[{"given":"Eric","family":"Ajieren","sequence":"first","affiliation":[{"name":"University of Houston, United States"}]},{"given":"Khalid","family":"Hourani","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Houston, United States"}]},{"given":"William K.","family":"Moses Jr.","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Houston, United States"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Houston, United States"}]}],"member":"320","published-online":{"date-parts":[[2022,1,24]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"John Augustine Mohsen Ghaffari Robert Gmyr Kristian Hinnenthal Christian Scheideler Fabian Kuhn and Jason Li. 2019. Distributed computation in node-capacitated networks. In SPAA. 69\u201379.  John Augustine Mohsen Ghaffari Robert Gmyr Kristian Hinnenthal Christian Scheideler Fabian Kuhn and Jason Li. 2019. Distributed computation in node-capacitated networks. In SPAA. 69\u201379.","DOI":"10.1145\/3323165.3323195"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS49936.2021.00031"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Sayan Bandyapadhyay Tanmay Inamdar Shreyas Pai and Sriram\u00a0V. Pemmaraju. 2018. Near-optimal clustering in the k-machine model. In ICDCN. 1\u201310.  Sayan Bandyapadhyay Tanmay Inamdar Shreyas Pai and Sriram\u00a0V. Pemmaraju. 2018. Near-optimal clustering in the k-machine model. In ICDCN. 1\u201310.","DOI":"10.1145\/3154273.3154317"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Paul Beame Paraschos Koutris and Dan Suciu. 2014. Skew in parallel query processing. In PODS. 212\u2013223.  Paul Beame Paraschos Koutris and Dan Suciu. 2014. Skew in parallel query processing. In PODS. 212\u2013223.","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_3_2_1_5_1","volume-title":"O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm (about a certain minimal problem). Pr\u00e1ce Mor. Pr\u00edrodoved. Spol. v Brne III 3","author":"Bor\u016fvka Otakar","year":"1926","unstructured":"Otakar Bor\u016fvka . 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm (about a certain minimal problem). Pr\u00e1ce Mor. Pr\u00edrodoved. Spol. v Brne III 3 ( 1926 ). Otakar Bor\u016fvka. 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm (about a certain minimal problem). Pr\u00e1ce Mor. Pr\u00edrodoved. Spol. v Brne III 3 (1926)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/100793104"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_3_2_1_9_1","volume-title":"Introduction to algorithms","author":"Cormen H","unstructured":"Thomas\u00a0 H Cormen , Charles\u00a0 E Leiserson , Ronald\u00a0 L Rivest , and Clifford Stein . 2009. Introduction to algorithms . MIT press . Thomas\u00a0H Cormen, Charles\u00a0E Leiserson, Ronald\u00a0L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MIT press."},{"key":"e_1_3_2_1_10_1","volume-title":"Dubhashi and Alessandro Panconesi","author":"P.","year":"2009","unstructured":"Devdatt\u00a0 P. Dubhashi and Alessandro Panconesi . 2009 . Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press . Devdatt\u00a0P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_11_1","volume-title":"d.]. Giraph","author":"Apache\u00a0Software Foundation The","unstructured":"The Apache\u00a0Software Foundation . [n. d.]. Giraph . http:\/\/giraph.apache.org\/. Accessed: 2020-02-14. The Apache\u00a0Software Foundation. [n. d.]. Giraph. http:\/\/giraph.apache.org\/. Accessed: 2020-02-14."},{"key":"e_1_3_2_1_12_1","unstructured":"The Apache\u00a0Software Foundation. [n. d.]. GraphX. https:\/\/spark.apache.org\/graphx\/. Accessed: 2020-03-13.  The Apache\u00a0Software Foundation. [n. d.]. GraphX. https:\/\/spark.apache.org\/graphx\/. Accessed: 2020-03-13."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Seth Gilbert and Lawrence Li. 2020. How fast can you update your MST? (Dynamic algorithms for cluster computing). arXiv preprint arXiv:2002.06762(2020).  Seth Gilbert and Lawrence Li. 2020. How fast can you update your MST? (Dynamic algorithms for cluster computing). arXiv preprint arXiv:2002.06762(2020).","DOI":"10.1145\/3350755.3400240"},{"key":"e_1_3_2_1_15_1","unstructured":"Tanmay Inamdar Shreyas Pai and Sriram\u00a0V. Pemmaraju. 2018. Large-Scale Distributed Algorithms for Facility Location with Outliers. In OPODIS.  Tanmay Inamdar Shreyas Pai and Sriram\u00a0V. Pemmaraju. 2018. Large-Scale Distributed Algorithms for Facility Location with Outliers. In OPODIS."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2672739"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Hossein Jowhari Mert Saglam and G\u00e1bor Tardos. 2011. Tight bounds for Lp samplers finding duplicates in streams and related problems. In PODS. 49\u201358.  Hossein Jowhari Mert Saglam and G\u00e1bor Tardos. 2011. Tight bounds for Lp samplers finding duplicates in streams and related problems. In PODS. 49\u201358.","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Howard\u00a0J. Karloff Siddharth Suri and Sergei Vassilvitskii. 2010. A model of computation for MapReduce. In SODA. 938\u2013948.  Howard\u00a0J. Karloff Siddharth Suri and Sergei Vassilvitskii. 2010. A model of computation for MapReduce. In SODA. 938\u2013948.","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Valerie King Shay Kutten and Mikkel Thorup. 2015. Construction and impromptu repair of an MST in a distributed network with o(m) communication. In PODC. 71\u201380.  Valerie King Shay Kutten and Mikkel Thorup. 2015. Construction and impromptu repair of an MST in a distributed network with o(m) communication. In PODC. 71\u201380.","DOI":"10.1145\/2767386.2767405"},{"key":"e_1_3_2_1_20_1","first-page":"1","article-title":"Connected Components in MapReduce and Beyond","volume":"18","author":"Kiveris Raimondas","year":"2014","unstructured":"Raimondas Kiveris , Silvio Lattanzi , Vahab Mirrokni , Vibhor Rastogi , and Sergei Vassilvitskii . 2014 . Connected Components in MapReduce and Beyond . In SoCC. 18 : 1 \u2013 18 :13. Raimondas Kiveris, Silvio Lattanzi, Vahab Mirrokni, Vibhor Rastogi, and Sergei Vassilvitskii. 2014. Connected Components in MapReduce and Beyond. In SoCC. 18:1\u201318:13.","journal-title":"SoCC."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck Danupon Nanongkai Gopal Pandurangan and Peter Robinson. 2015. Distributed computation of large-scale graph problems. In SODA. 391\u2013410.  Hartmut Klauck Danupon Nanongkai Gopal Pandurangan and Peter Robinson. 2015. Distributed computation of large-scale graph problems. In SODA. 391\u2013410.","DOI":"10.1137\/1.9781611973730.28"},{"key":"e_1_3_2_1_22_1","unstructured":"Christian Konrad Sriram\u00a0V. Pemmaraju Talal Riaz and Peter Robinson. 2019. The Complexity of Symmetry Breaking in Massive Graphs. In DISC Vol.\u00a0146. 26:1\u201326:18.  Christian Konrad Sriram\u00a0V. Pemmaraju Talal Riaz and Peter Robinson. 2019. The Complexity of Symmetry Breaking in Massive Graphs. In DISC Vol.\u00a0146. 26:1\u201326:18."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Silvio Lattanzi Benjamin Moseley Siddharth Suri and Sergei Vassilvitskii. 2011. Filtering: a method for solving graph problems in mapreduce. In SPAA. 85\u201394.  Silvio Lattanzi Benjamin Moseley Siddharth Suri and Sergei Vassilvitskii. 2011. Filtering: a method for solving graph problems in mapreduce. In SPAA. 85\u201394.","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_24_1","volume-title":"Distributed Algorithms","author":"Lynch A.","unstructured":"Nancy\u00a0 A. Lynch . 1996. Distributed Algorithms . Morgan Kaufmann Publishers Inc . Nancy\u00a0A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Grzegorz Malewicz Matthew\u00a0H. Austern Aart J.\u00a0C. Bik James\u00a0C. Dehnert Ilan Horn Naty Leiser and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In SIGMOD. 135\u2013146.  Grzegorz Malewicz Matthew\u00a0H. Austern Aart J.\u00a0C. Bik James\u00a0C. Dehnert Ilan Horn Naty Leiser and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In SIGMOD. 135\u2013146.","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_27_1","volume-title":"Probability and computing: randomization and probabilistic techniques in algorithms and data analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2017. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press . Michael Mitzenmacher and Eli Upfal. 2017. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press."},{"key":"e_1_3_2_1_28_1","unstructured":"Gopal Pandurangan. 2021. Distributed Network Algorithms. In Distributed Network Algorithms. https:\/\/sites.google.com\/site\/gopalpandurangan\/home\/distributed-network-algorithms  Gopal Pandurangan. 2021. Distributed Network Algorithms. In Distributed Network Algorithms. https:\/\/sites.google.com\/site\/gopalpandurangan\/home\/distributed-network-algorithms"},{"key":"e_1_3_2_1_29_1","volume-title":"Conference version published in SPAA","author":"Pandurangan Gopal","year":"2018","unstructured":"Gopal Pandurangan , Peter Robinson , and Michele Scquizzato . 2018 . Fast Distributed Algorithms for Connectivity and MST in Large Graphs. ACM Transactions on Parallel Computing (TOPC) 5, 1 (2018), 4:1\u20134:22 . Conference version published in SPAA 2016. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. 2018. Fast Distributed Algorithms for Connectivity and MST in Large Graphs. ACM Transactions on Parallel Computing (TOPC) 5, 1 (2018), 4:1\u20134:22. Conference version published in SPAA 2016."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460900"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699414"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050202"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Isabelle Stanton. 2014. Streaming balanced graph partitioning algorithms for random graphs. In SODA. 1287\u20131301.  Isabelle Stanton. 2014. Streaming balanced graph partitioning algorithms for random graphs. In SODA. 1287\u20131301.","DOI":"10.1137\/1.9781611973402.95"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"}],"event":{"name":"ICDCN '22: 23rd International Conference on Distributed Computing and Networking","location":"Delhi AA India","acronym":"ICDCN '22"},"container-title":["Proceedings of the 23rd International Conference on Distributed Computing and Networking"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491003.3491011","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491003.3491011","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491003.3491011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:30Z","timestamp":1750188630000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491003.3491011"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,4]]},"references-count":35,"alternative-id":["10.1145\/3491003.3491011","10.1145\/3491003"],"URL":"https:\/\/doi.org\/10.1145\/3491003.3491011","relation":{},"subject":[],"published":{"date-parts":[[2022,1,4]]},"assertion":[{"value":"2022-01-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}