{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T08:34:20Z","timestamp":1789547660257,"version":"build-2803163510"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662534250","type":"print"},{"value":"9783662534267","type":"electronic"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53426-7_25","type":"book-chapter","created":{"date-parts":[[2016,9,3]],"date-time":"2016-09-03T08:49:15Z","timestamp":1472892555000},"page":"342-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Distributed Testing of Excluded Subgraphs"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ville","family":"Salo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,9,4]]},"reference":[{"issue":"2","key":"25_CR1","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1137\/07067917X","volume":"22","author":"N Alon","year":"2008","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Ron, D.: Testing triangle-freeness in general graphs. SIAM J. Discrete Math. 22(2), 786\u2013819 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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, Heidelberg (2014)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-319-03089-0_10","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"H Arfaoui","year":"2013","unstructured":"Arfaoui, H., Fraigniaud, P., Pelc, A.: Local decision and verification with bounded-size outputs. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 133\u2013147. Springer, Heidelberg (2013)"},{"issue":"3","key":"25_CR4","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."},{"issue":"12","key":"25_CR5","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1073\/pnas.32.12.331","volume":"32","author":"FA Behrend","year":"1946","unstructured":"Behrend, F.A.: On sets of integers which contain no three terms in arithmetical progression. Proc. Natl. Acad. Sci. 32(12), 331 (1946)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Fischer, E., Schwartzman, G., Vasudev, Y.: Fast distributed algorithms for testing graph properties. CoRR abs\/1602.03718, February 2016","DOI":"10.1007\/978-3-662-53426-7_4"},{"key":"25_CR7","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 PODC 2015, pp. 143\u2013152 (2015)","DOI":"10.1145\/2767386.2767414"},{"issue":"5","key":"25_CR8","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A Das-Sarma","year":"2012","unstructured":"Das-Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-33651-5_14","volume-title":"Distributed Computing","author":"D Dolev","year":"2012","unstructured":"Dolev, D., Lenzen, C., Peled, S.: \u201cTri, Tri Again\u201d: finding triangles and small subgraphs in a distributed setting. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 195\u2013209. Springer, Heidelberg (2012)"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of PODC 2014, pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"2","key":"25_CR11","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., G\u00f6\u00f6s, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: Proceedings of PODC 2013, pp. 157\u2013165 (2013)","DOI":"10.1145\/2484239.2484264"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. In: Proceedings of FOCS 2011, pp. 708\u2013717 (2011)","DOI":"10.1109\/FOCS.2011.17"},{"issue":"4","key":"25_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00446-013-0188-x","volume":"26","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and checkability in wait-free computing. Distrib. Comput. 26(4), 223\u2013242 (2013)","journal-title":"Distrib. Comput."},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/978-3-319-11164-3_9","volume-title":"Runtime Verification","author":"P Fraigniaud","year":"2014","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: On the number of opinions needed for fault-tolerant run-time monitoring in distributed systems. In: Bonakdarpour, B., Smolka, S.A. (eds.) RV 2014. LNCS, vol. 8734, pp. 92\u2013107. Springer, Heidelberg (2014)"},{"key":"25_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"Property Testing","year":"2010","unstructured":"Goldreich, O. (ed.): Property Testing. LNCS, vol. 6390. Springer, Heidelberg (2010)"},{"issue":"4","key":"25_CR17","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Jukka Suomela, J.: Locally checkable proofs. In: Proceedings of PODC 2011, pp. 159\u2013168 (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"25_CR19","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: Proceedings of PODC 2015, pp. 91\u2013100 (2015)","DOI":"10.1145\/2767386.2767434"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1007\/978-3-319-25258-2_26","volume-title":"SIROCCO 2015","author":"J Kari","year":"2015","unstructured":"Kari, J., Matamala, M., Rapaport, I., Salo, V.: Solving the induced subgraphproblem in the randomized multiparty simultaneous messages model. In: Scheideler, C. (ed.) SIROCCO 2015. LNCS, vol. 9439, pp. 370\u2013384. Springer, Heidelberg (2015)"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: Proceedings of PODC 2013, pp. 42\u201350 (2013)","DOI":"10.1145\/2484239.2501983"},{"issue":"6","key":"25_CR23","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s00446-005-0127-6","volume":"18","author":"Z Lotker","year":"2006","unstructured":"Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. Distrib. Comput. 18(6), 453\u2013460 (2006)","journal-title":"Distrib. Comput."},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: MST construction in $${{\\cal O}}(\\log \\log n)$$ communication rounds. In: Proceedings of SPAA 2003, pp. 94\u2013100 (2003)","DOI":"10.1145\/777412.777428"},{"key":"25_CR25","doi-asserted-by":"publisher","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":"25_CR26","doi-asserted-by":"crossref","unstructured":"Patt-Shamir, B., Teplitsky, M.: The round complexity of distributed sorting. In: Proceedings of PODC 2011, pp. 249\u2013256 (2011)","DOI":"10.1145\/1993806.1993851"},{"key":"25_CR27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"Reiter, F.: Distributed graph automata. In: Proceedings of LICS 2015, pp. 192\u2013201 (2015)","DOI":"10.1109\/LICS.2015.27"},{"issue":"1","key":"25_CR29","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s11856-013-0049-0","volume":"199","author":"T Schoen","year":"2014","unstructured":"Schoen, T., Shkredov, I.D.: Roth\u2019s theorem in many variables. Isr. J. Math. 199(1), 287\u2013308 (2014)","journal-title":"Isr. J. Math."}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53426-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T16:42:44Z","timestamp":1749573764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53426-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662534250","9783662534267"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53426-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"4 September 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DISC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Distributed Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 September 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 September 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wdag2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}