{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:29:55Z","timestamp":1742912995079,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_11","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"134-145","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model"],"prefix":"10.1007","author":[{"given":"Florent","family":"Becker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st Symposium on Principles of Database Systems, PODS 2012, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 82\u201393. ACM (1980)","DOI":"10.1145\/800141.804655"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-319-12340-0_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H Arfaoui","year":"2014","unstructured":"Arfaoui, H., Fraigniaud, P., Ilcinkas, D., Mathieu, F.: Distributedly testing cycle-freeness. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 15\u201328. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-12340-0_2"},{"issue":"2","key":"11_CR5","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B Awerbuch","year":"1990","unstructured":"Awerbuch, B., Goldreich, O., Vainish, R., Peleg, D.: A trade-off between information and communication in broadcast protocols. J. ACM 37(2), 238\u2013256 (1990)","journal-title":"J. ACM"},{"issue":"3","key":"11_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00446-014-0221-8","volume":"28","author":"F Becker","year":"2015","unstructured":"Becker, F., Kosowski, A., Matamala, M., Nisse, N., Rapaport, I., Suchan, K., Todinca, I.: Allowing each node to communicate only once in a distributed system: shared whiteboard models. Distrib. Comput. 28(3), 189\u2013200 (2015)","journal-title":"Distrib. Comput."},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Becker, F., Matamala, M., Nisse, N., Rapaport, I., Suchan, K., Todinca, I.: Adding a referee to an interconnection network: what can(not) be computed in one round. In: Proceedings of the 25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011, pp. 508\u2013514 (2011)","DOI":"10.1109\/IPDPS.2011.55"},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-319-09620-9_8","volume-title":"Structural Information and Communication Complexity","author":"F Becker","year":"2014","unstructured":"Becker, F., Montealegre, P., Rapaport, I., Todinca, I.: The simultaneous number-in-hand communication model for networks: private coins, public coins and determinism. In: Halld\u00f3rsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 83\u201395. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09620-9_8"},{"issue":"1","key":"11_CR9","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1002\/jgt.10099","volume":"43","author":"E Birmel\u00e9","year":"2003","unstructured":"Birmel\u00e9, E.: Tree-width and circumference of graphs. J. Graph Theory 43(1), 24\u201325 (2003)","journal-title":"J. Graph Theory"},{"issue":"2","key":"11_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"JA Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. J. Comb. Theory, Ser. B 16(2), 97\u2013105 (1974)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Spinrad, J.P., et al.: Graph classes: a survey, vol. 3. Siam (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"11_CR12","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: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pp. 143\u2013152 (2015)","DOI":"10.1145\/2767386.2767414"},{"issue":"10","key":"11_CR13","doi-asserted-by":"publisher","first-page":"1178","DOI":"10.1109\/12.5979","volume":"37","author":"N Chandrasekharan","year":"1988","unstructured":"Chandrasekharan, N., Sitharama Iyengar, S.: NC algorithms for recognizing chordal graphs and k trees. IEEE Trans. Comput. 37(10), 1178\u20131183 (1988)","journal-title":"IEEE Trans. Comput."},{"key":"11_CR14","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 2014, pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"key":"11_CR15","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications. Proceedings of the Symposium, Smolenice (1964)"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hyperedge connectivity in dynamic graph streams. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems, pp. 241\u2013247. ACM (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"11_CR17","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). https:\/\/doi.org\/10.1007\/978-3-662-45174-8_35"},{"key":"11_CR18","unstructured":"Holzer, S., Pinsker, N.: Approximation of distances and shortest paths in the broadcast congest clique. In: 19th International Conference on Principles of Distributed Systems, OPODIS 2015, Leibniz International Proceedings in Informatics (LIPIcs), vol. 46, pp. 1\u201316 (2016)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for lp samplers, finding duplicates in streams, and related problems. In: Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, pp. 49\u201358 (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Nowicki, K.: MST in O(1) rounds of the congested clique. Preprint arXiv:1707.08484 (2017)","DOI":"10.1137\/1.9781611975031.167"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-319-25258-2_26","volume-title":"Structural Information and Communication Complexity","author":"J Kari","year":"2015","unstructured":"Kari, J., Matamala, M., Rapaport, I., Salo, V.: Solving the induced subgraph problem in the randomized multiparty simultaneous messages model. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 370\u2013384. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-25258-2_26"},{"issue":"1","key":"11_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1090\/S0273-0979-1995-00569-0","volume":"32","author":"F Lazebnik","year":"1995","unstructured":"Lazebnik, F., Ustimenko, V.A., Woldar, A.J.: A new series of dense graphs of high girth. Bull. Am. Math. Soc. 32(1), 73\u201379 (1995)","journal-title":"Bull. Am. Math. Soc."},{"issue":"1","key":"11_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Com. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Com."},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Montealegre, P., Todinca, I.: Brief anouncement: deterministic graph connectivity in the broadcast congested clique. In: Proceedings of the 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2016 (2016)","DOI":"10.1145\/2933057.2933066"},{"issue":"6","key":"11_CR25","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:01:24Z","timestamp":1709827284000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}