{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T04:16:04Z","timestamp":1749701764631,"version":"3.41.0"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319483139"},{"type":"electronic","value":"9783319483146"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48314-6_20","type":"book-chapter","created":{"date-parts":[[2016,11,3]],"date-time":"2016-11-03T15:01:04Z","timestamp":1478185264000},"page":"307-322","source":"Crossref","is-referenced-by-count":2,"title":["Sparsifying Congested Cliques and Core-Periphery Networks"],"prefix":"10.1007","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,4]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-662-43951-7_34","volume-title":"Automata, Languages, and Programming","author":"C Avin","year":"2014","unstructured":"Avin, C., Borokhovich, M., Lotker, Z., Peleg, D.: Distributed computing on core-periphery networks: axiom-based design. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 399\u2013410. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-43951-7_34"},{"issue":"5","key":"20_CR2","doi-asserted-by":"crossref","first-page":"976","DOI":"10.1137\/S0097539792232021","volume":"23","author":"AZ Broder","year":"1994","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: Existence and construction of edge-disjoint paths on expander graphs. SIAM J. Comput. 23(5), 976\u2013989 (1994)","journal-title":"SIAM J. Comput."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 143\u2013152 (2015)","DOI":"10.1145\/2767386.2767414"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-319-25258-2_19","volume-title":"Structural Information and Communication Complexity","author":"K Censor-Hillel","year":"2015","unstructured":"Censor-Hillel, K., Toukan, T.: On fast and robust information spreading in the vertex-congest model. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 270\u2013284. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-25258-2_19"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"key":"20_CR6","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 359\u2013368 (2004)"},{"issue":"4","key":"20_CR7","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1002\/rsa.3240010406","volume":"1","author":"U Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms 1(4), 447\u2013460 (1990)","journal-title":"Random Struct. Algorithms"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-49543-6_1","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"AM Frieze","year":"1998","unstructured":"Frieze, A.M.: Disjoint paths in expander graphs via random walks: a short survey. In: Luby, M., Rolim, J.D.P., Serna, M. (eds.) RANDOM 1998. LNCS, vol. 1518, pp. 1\u201314. Springer, Heidelberg (1998). doi: 10.1007\/3-540-49543-6_1"},{"key":"20_CR9","unstructured":"Frieze, A.M.: Edge-disjoint paths in expander graphs. In: 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717\u2013725 (2000)"},{"issue":"1","key":"20_CR10","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"RG Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"20_CR11","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"JA Garay","year":"1998","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Parter, M.: MST in log-star rounds of congested clique. In: 35th ACM Symposium on Principles of Distributed Computing (PODC) (2016)","DOI":"10.1145\/2933057.2933103"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward optimal bounds in the congested clique: graph connectivity and MST. In ACM Symposium on Principles of Distributed Computing (PODC), pp. 91\u2013100 (2015)","DOI":"10.1145\/2767386.2767434"},{"key":"20_CR14","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.tcs.2015.09.029","volume":"608","author":"JW Hegeman","year":"2015","unstructured":"Hegeman, J.W., Pemmaraju, S.V.: Lessons from the congested clique applied to MapReduce. Theor. Comput. Sci. 608, 268\u2013281 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/978-3-662-45174-8_35","volume-title":"Distributed Computing","author":"JW Hegeman","year":"2014","unstructured":"Hegeman, J.W., Pemmaraju, S.V., Sardeshmukh, V.B.: Near-constant-time distributed algorithms on a congested clique. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 514\u2013530. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-45174-8_35"},{"issue":"1","key":"20_CR16","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28(1), 40\u201366 (1998)","journal-title":"J. Algorithms"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Leighton, T., Rao, S., Srinivasan, A.: Multicommodity flow and circuit switching. In: 31st Hawaii International Conference on System Sciences, pp. 459\u2013465 (1998)","DOI":"10.1109\/HICSS.1998.649241"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In ACM Symposium on Principles of Distributed Computing (PODC), pp. 42\u201350, (2013)","DOI":"10.1145\/2484239.2501983"},{"issue":"1","key":"20_CR19","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput. 35(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. In: 20th ACM Symposium on Principles of Distributed Computing (PODC), pp. 63\u201371 (2001)","DOI":"10.1145\/383962.383984"},{"key":"20_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing - Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing - Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-662-46078-8_31","volume-title":"SOFSEM 2015: Theory and Practice of Computer Science","author":"H Ookawa","year":"2015","unstructured":"Ookawa, H., Izumi, T.: Filling logarithmic gaps in distributed complexity for global problems. In: Italiano, G.F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 377\u2013388. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-46078-8_31"},{"issue":"5","key":"20_CR23","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427\u20131442 (2000)","journal-title":"SIAM J. Comput."},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G, Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: 43rd ACM Symposium on Theory of Computing (STOC), pp. 363\u2013372 (2011)","DOI":"10.1145\/1993636.1993686"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48314-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T23:53:11Z","timestamp":1749685991000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48314-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319483139","9783319483146"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48314-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}