{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:20Z","timestamp":1759639040851,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T00:00:00Z","timestamp":1560729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB 901"],"award-info":[{"award-number":["SFB 901"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["INT\/FRG\/DAAD\/P-25\/2018"],"award-info":[{"award-number":["INT\/FRG\/DAAD\/P-25\/2018"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["200021_184735"],"award-info":[{"award-number":["200021_184735"]}]},{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["MTR\/2018\/001198, EMR\/2016\/003016"],"award-info":[{"award-number":["MTR\/2018\/001198, EMR\/2016\/003016"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["336495"],"award-info":[{"award-number":["336495"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,17]]},"DOI":"10.1145\/3323165.3323195","type":"proceedings-article","created":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T12:14:30Z","timestamp":1560860070000},"page":"69-79","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Distributed Computation in Node-Capacitated Networks"],"prefix":"10.1145","author":[{"given":"John","family":"Augustine","sequence":"first","affiliation":[{"name":"IIT Madras, Madras, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Gmyr","sequence":"additional","affiliation":[{"name":"University of Houston, Houston, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristian","family":"Hinnenthal","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason","family":"Li","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,17]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1145\/800220.806683"},{"key":"e_1_3_2_1_2_1","volume-title":"Spartan: A Framework For Sparse Robust Addressable Networks. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 1060--1069","author":"Augustine John","year":"2018","unstructured":"John Augustine and Sumathi Sivasubramaniam . 2018 . Spartan: A Framework For Sparse Robust Addressable Networks. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 1060--1069 . John Augustine and Sumathi Sivasubramaniam. 2018. Spartan: A Framework For Sparse Robust Addressable Networks. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 1060--1069."},{"unstructured":"Leonid Barenboim and Michael Elkin. 2009. Distributed (\u03b4  Leonid Barenboim and Michael Elkin. 2009. Distributed (\u03b4","key":"e_1_3_2_1_3_1"},{"volume-title":"Time. In Proc. of 41st Annual ACM Symposium on Theory of Computing (STOC). 111--120","author":"Coloring","unstructured":"1)- Coloring in Linear (in \u03b4) Time. In Proc. of 41st Annual ACM Symposium on Theory of Computing (STOC). 111--120 . 1)-Coloring in Linear (in \u03b4) Time. In Proc. of 41st Annual ACM Symposium on Theory of Computing (STOC). 111--120.","key":"e_1_3_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1007\/s00446-009-0088-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1145\/2027216.2027221"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_8_1","volume-title":"Distributed Symmetry-Breaking Algorithms for Congested Cliques. arXiv preprint arXiv:1802.07209","author":"Barenboim Leonid","year":"2018","unstructured":"Leonid Barenboim and Victor Khazanov . 2018. Distributed Symmetry-Breaking Algorithms for Congested Cliques. arXiv preprint arXiv:1802.07209 ( 2018 ). Leonid Barenboim and Victor Khazanov. 2018. Distributed Symmetry-Breaking Algorithms for Congested Cliques. arXiv preprint arXiv:1802.07209 (2018)."},{"key":"e_1_3_2_1_9_1","volume-title":"The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model. In LATIN 2018: Theoretical Informatics. 134--145","author":"Becker Florent","year":"2018","unstructured":"Florent Becker , Pedro Montealegre , Ivan Rapaport , and Ioan Todinca . 2018 . The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model. In LATIN 2018: Theoretical Informatics. 134--145 . Florent Becker, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. 2018. The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model. In LATIN 2018: Theoretical Informatics. 134--145."},{"key":"e_1_3_2_1_10_1","volume-title":"Proc. of 31st International Symposium on Distributed Computing (DISC). 7:1--7:16","author":"Becker Ruben","year":"2017","unstructured":"Ruben Becker , Andreas Karrenbauer , Sebastian Krinninger , and Christoph Lenzen . 2017 . Near-optimal approximate shortest paths and transshipment in distributed and streaming models . In Proc. of 31st International Symposium on Distributed Computing (DISC). 7:1--7:16 . Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In Proc. of 31st International Symposium on Distributed Computing (DISC). 7:1--7:16."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1137\/120871626"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/2767386.2767414"},{"key":"e_1_3_2_1_13_1","volume-title":"Proc. of 31st International Symposium on Distributed Computing (DISC) . 11:1--11:16","author":"Censor-Hillel Keren","year":"2017","unstructured":"Keren Censor-Hillel , Merav Parter , and Gregory Schwartzman . 2017 . Derandomizing local distributed algorithms under bandwidth restrictions . In Proc. of 31st International Symposium on Distributed Computing (DISC) . 11:1--11:16 . Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. 2017. Derandomizing local distributed algorithms under bandwidth restrictions. In Proc. of 31st International Symposium on Distributed Computing (DISC) . 11:1--11:16."},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. of MFCS Workshop on Communications . 91--100","author":"Deo Narsingh","year":"1998","unstructured":"Narsingh Deo and Bruce Litow . 1998 . A Structural Approach to Graph Compression . In Proc. of MFCS Workshop on Communications . 91--100 . Narsingh Deo and Bruce Litow. 1998. A Structural Approach to Graph Compression. In Proc. of MFCS Workshop on Communications . 91--100."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1007\/978-3-642-33651-5_14"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1145\/2611462.2611493"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.5555\/3115447.3115617"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1016\/j.jcss.2006.07.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1007\/978-3-662-53426-7_5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.5555\/2884435.2884451"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1145\/3087801.3087827"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1145\/3212734.3212750"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_3_2_1_24_1","volume-title":"Proc. of 44th International Colloqium on Algorithms, Languages, and Programming (ICALP) . 137:1--137:15","author":"Gmyr Robert","year":"2017","unstructured":"Robert Gmyr , Kristian Hinnenthal , Christian Scheideler , and Christian Sohler . 2017 . Distributed Monitoring of Network Properties: The Power of Hybrid Networks . In Proc. of 44th International Colloqium on Algorithms, Languages, and Programming (ICALP) . 137:1--137:15 . Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, and Christian Sohler. 2017. Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In Proc. of 44th International Colloqium on Algorithms, Languages, and Programming (ICALP) . 137:1--137:15."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1145\/2767386.2767434"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1016\/j.tcs.2015.09.029"},{"volume-title":"Proc. of 28th International Symposium on Distributed Computing (DISC). 514--530","author":"Hegeman James W.","unstructured":"James W. Hegeman , Sriram V. Pemmaraju , and Vivek B. Sardeshmukh . 2014. Near-constant-time distributed algorithms on a congested clique . In Proc. of 28th International Symposium on Distributed Computing (DISC). 514--530 . James W. Hegeman, Sriram V. Pemmaraju, and Vivek B. Sardeshmukh. 2014. Near-constant-time distributed algorithms on a congested clique. In Proc. of 28th International Symposium on Distributed Computing (DISC). 514--530.","key":"e_1_3_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_3_2_1_29_1","volume-title":"Proc. of 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) . 15--31","author":"Jung Daniel","year":"2018","unstructured":"Daniel Jung , Christina Kolb , Christian Scheideler , and Jannik Sundermeier . 2018 . Competitive Routing in Hybrid Communication Networks . In Proc. of 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) . 15--31 . Daniel Jung, Christina Kolb, Christian Scheideler, and Jannik Sundermeier. 2018. Competitive Routing in Hybrid Communication Networks. In Proc. of 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) . 15--31."},{"doi-asserted-by":"crossref","unstructured":"Tomasz Jurdzi'n ski and Krzysztof Nowicki. 2018a. Connectivity and Minimum Cut Approximation in the Broadcast Congested Clique. In Structural Information and Communication Complexity (SIROCCO) . 331--344.  Tomasz Jurdzi'n ski and Krzysztof Nowicki. 2018a. Connectivity and Minimum Cut Approximation in the Broadcast Congested Clique. In Structural Information and Communication Complexity (SIROCCO) . 331--344.","key":"e_1_3_2_1_30_1","DOI":"10.1007\/978-3-030-01325-7_28"},{"key":"e_1_3_2_1_31_1","volume-title":"Proc. of 29th ACM-SIAM Symposium on Discrete Algorithms (SODA). 2620--2632","author":"Krzysztof Nowicki Tomasz Jurdzi'n","year":"2018","unstructured":"Tomasz Jurdzi'n ski and Krzysztof Nowicki . 2018 b. MST in $O(1)$ rounds of congested clique . In Proc. of 29th ACM-SIAM Symposium on Discrete Algorithms (SODA). 2620--2632 . Tomasz Jurdzi'n ski and Krzysztof Nowicki. 2018b. MST in $O(1)$ rounds of congested clique. In Proc. of 29th ACM-SIAM Symposium on Discrete Algorithms (SODA). 2620--2632."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1145\/2767386.2767405"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.5555\/2722129.2722157"},{"key":"e_1_3_2_1_34_1","volume-title":"Proc. of 30th International Symposium on Distributed Computing (DISC 2016)","author":"Korhonen Janne H.","year":"2016","unstructured":"Janne H. Korhonen . 2016 . Brief announcement: Deterministic MST sparsification in the congested clique . In Proc. of 30th International Symposium on Distributed Computing (DISC 2016) . Janne H. Korhonen. 2016. Brief announcement: Deterministic MST sparsification in the congested clique. In Proc. of 30th International Symposium on Distributed Computing (DISC 2016) ."},{"volume-title":"Proc. of 31st International Symposium on Distributed Computing (DISC) . 55:1--55:3.","author":"Janne","unstructured":"Janne H. Korhonen and Jukka Suomela. 2017. Brief Announcement: Towards a Complexity Theory for the Congested Clique . In Proc. of 31st International Symposium on Distributed Computing (DISC) . 55:1--55:3. Janne H. Korhonen and Jukka Suomela. 2017. Brief Announcement: Towards a Complexity Theory for the Congested Clique. In Proc. of 31st International Symposium on Distributed Computing (DISC) . 55:1--55:3.","key":"e_1_3_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1145\/1993806.1993812"},{"key":"e_1_3_2_1_37_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","volume":"18","author":"Kothapalli Kishore","year":"2012","unstructured":"Kishore Kothapalli and Sriram Pemmaraju . 2012 . Super-Fast 3-Ruling Sets . In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , Vol. 18 . 136--147. Kishore Kothapalli and Sriram Pemmaraju. 2012. Super-Fast 3-Ruling Sets. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Vol. 18. 136--147."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.5555\/1898953.1898978"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1006\/jagm.1998.0929"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1145\/2484239.2501983"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1137\/S0097539704441848"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1007\/s00446-010-0121-5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_43_1","DOI":"10.1145\/2591796.2591850"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1112\/jlms\/s1-39.1.12"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_45_1","DOI":"10.1145\/2935764.2935785"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1016\/0022-0000(91)90005-P"},{"key":"e_1_3_2_1_47_1","volume-title":"Proc. of 43th ACM Symposium on Theory of Computing (STOC). 363--372","author":"Sarma Atish Das","year":"2011","unstructured":"Atish Das Sarma , Stephan Holzer , Liah Kor , Amos Korman , Danupon Nanongkai , Gopal Pandurangan , David Peleg , and Roger Wattenhofer . 2011 . Distributed verification and hardness of distributed approximation . In Proc. of 43th ACM Symposium on Theory of Computing (STOC). 363--372 . Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2011. Distributed verification and hardness of distributed approximation. In Proc. of 43th ACM Symposium on Theory of Computing (STOC). 363--372."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_48_1","DOI":"10.1137\/S089548019223872X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_49_1","DOI":"10.1145\/800220.806682"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"acronym":"SPAA '19","name":"SPAA '19: 31st ACM Symposium on Parallelism in Algorithms and Architectures","location":"Phoenix AZ USA"},"container-title":["The 31st ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3323165.3323195","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3323165.3323195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:16Z","timestamp":1750202596000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3323165.3323195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,17]]},"references-count":49,"alternative-id":["10.1145\/3323165.3323195","10.1145\/3323165"],"URL":"https:\/\/doi.org\/10.1145\/3323165.3323195","relation":{},"subject":[],"published":{"date-parts":[[2019,6,17]]},"assertion":[{"value":"2019-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}