{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:45:04Z","timestamp":1742913904820,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319123394"},{"type":"electronic","value":"9783319123400"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12340-0_2","type":"book-chapter","created":{"date-parts":[[2014,10,20]],"date-time":"2014-10-20T04:27:23Z","timestamp":1413779243000},"page":"15-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Distributedly Testing Cycle-Freeness"],"prefix":"10.1007","author":[{"given":"Heger","family":"Arfaoui","sequence":"first","affiliation":[]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[]},{"given":"Fabien","family":"Mathieu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"issue":"4","key":"2_CR1","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/jgt.3190180406","volume":"18","author":"N Alon","year":"1994","unstructured":"Alon, N.: Subdivided graphs have linear ramsey numbers. J. Graph Theor. 18(4), 343\u2013347 (1994)","journal-title":"J. Graph Theor."},{"issue":"6","key":"2_CR2","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1017\/S0963548306007759","volume":"15","author":"N Alon","year":"2006","unstructured":"Alon, N., Shapira, A.: A characterization of easily testable induced subgraphs. Comb. Probab. Comput. 15(6), 791\u2013805 (2006)","journal-title":"Comb. Probab. Comput."},{"key":"2_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)"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Becker, F., Kosowski, A., Nisse, N., Rapaport, I., Suchan, K.: Allowing each node to communicate only once in a distributed system: shared whiteboard models. In: Proceediings 24th ACM Sympsium on Parallelism in Algorithms and Architectures (SPAA), pp. 11\u201317 (2012)","DOI":"10.1145\/2312005.2312008"},{"key":"2_CR5","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 25th IEEE International Sympusim on Parallel and Distributed Processing (IPDPS), pp. 508\u2013514 (2011)","DOI":"10.1109\/IPDPS.2011.55"},{"issue":"3","key":"2_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D Corneil","year":"1981","unstructured":"Corneil, D., Lerchs, H., Burlingham, L.: Complement reducible graphs. Discrete Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discrete Appl. Math."},{"issue":"13","key":"2_CR7","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(13), 77\u2013144 (2000)","journal-title":"Discrete Appl. Math."},{"key":"2_CR8","first-page":"35","volume":"19","author":"A Czumaj","year":"2012","unstructured":"Czumaj, A., Goldreich, O., Ron, D., Seshadhri, C., Shapira, A., Sohler, C.: Finding cycles and trees in sublinear time. Electron. Colloq. Comput. Complex. (ECCC) 19, 35 (2012)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"issue":"6","key":"2_CR9","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s002360050180","volume":"36","author":"S Dolev","year":"1999","unstructured":"Dolev, S., Gouda, M.G., Schneider, M.: Memory requirements for silent stabilization. Acta Inf. 36(6), 447\u2013462 (1999)","journal-title":"Acta Inf."},{"key":"2_CR10","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 the 32nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 157\u2013165 (2013)","DOI":"10.1145\/2484239.2484264"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-642-33651-5_26","volume-title":"Distributed Computing","author":"P Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized distributed decision. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 371\u2013385. Springer, Heidelberg (2012)"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 708\u2013717 (2011)","DOI":"10.1109\/FOCS.2011.17"},{"issue":"5","key":"2_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35 (2013)","journal-title":"J. ACM"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","volume-title":"Property Testing\u2014Current Research and Surveys","year":"2010","unstructured":"Goldreich, O. (ed.): Property Testing. LNCS, vol. 6390. Springer, Heidelberg (2010)"},{"issue":"2","key":"2_CR15","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"issue":"5","key":"2_CR16","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/2528405","volume":"60","author":"M G\u00f6\u00f6s","year":"2013","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. J. ACM 60(5), 39 (2013)","journal-title":"J. ACM"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs. In: Proceedings of the 30th ACM Sympusim on Principles of Distributed Computing (PODC), pp. 159\u2013168 (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"2_CR18","unstructured":"Itkis, G., Levin, L.A.: Fast and lean self-stabilizing asynchronous protocols. In: 35th IEEE Sympsium on Foundations of Computer Science (FOCS), pp. 226\u2013239 (1994)"},{"issue":"4","key":"2_CR19","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"issue":"6","key":"2_CR20","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."},{"key":"2_CR21","doi-asserted-by":"crossref","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)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12340-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T14:49:41Z","timestamp":1676904581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12340-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319123394","9783319123400"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12340-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"21 October 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}