{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T08:34:19Z","timestamp":1789547659906,"version":"build-2803163510"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319252575","type":"print"},{"value":"9783319252582","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_3","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T07:10:18Z","timestamp":1445238618000},"page":"31-45","source":"Crossref","is-referenced-by-count":10,"title":["Node Labels in Local Decision"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juho","family":"Hirvonen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proc. 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pp. 82\u201393. ACM Press (1980). doi:10.1145\/800141.804655","DOI":"10.1145\/800141.804655"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-45414-4_3","volume-title":"Distributed Computing","author":"P. Boldi","year":"2001","unstructured":"Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 33\u201347. Springer, Heidelberg (2001)"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/11864219_8","volume-title":"Distributed Computing","author":"J. Chalopin","year":"2006","unstructured":"Chalopin, J., Das, S., Santoro, N.: Groupings and pairings in anonymous networks. In: Dolev, S. (ed.) DISC 2006. LNCS, vol.\u00a04167, pp. 105\u2013119. Springer, Heidelberg (2006)"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-87779-0_6","volume-title":"Distributed Computing","author":"A. Czygrinow","year":"2008","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 78\u201392. Springer, Heidelberg (2008)"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Diks, K., Kranakis, E., Malinowski, A., Pelc, A.: Anonymous wireless rings. Theoretical Computer Science\u00a0145(1\u20132), 95\u2013109 (1995). doi:10.1016\/0304-3975(94)00178-L","DOI":"10.1016\/0304-3975(94)00178-L"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Emek, Y., Pfister, C., Seidel, J., Wattenhofer, R.: Anonymous networks: randomization = 2-hop coloring. In: Proc. 33rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2014), pp. 96\u2013105. ACM Press (2014). doi:10.1145\/2611462.2611478","DOI":"10.1145\/2611462.2611478"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-662-43951-7_16","volume-title":"Automata, Languages, and Programming","author":"Y. Emek","year":"2014","unstructured":"Emek, Y., Seidel, J., Wattenhofer, R.: Computability in anonymous networks: Revocable vs. Irrecovable outputs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol.\u00a08573, pp. 183\u2013195. Springer, Heidelberg (2014)"},{"issue":"2\u20133","key":"3_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","volume":"16","author":"F. Fich","year":"2003","unstructured":"Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distributed Computing\u00a016(2\u20133), 121\u2013163 (2003), doi:10.1007\/s00446-003-0091-y","journal-title":"Distributed Computing"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-73420-8_22","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2007","unstructured":"Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed computing with advice: Information sensitivity of graph coloring. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 231\u2013242. Springer, Heidelberg (2007)"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., G\u00f6\u00f6s, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: Proc. 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC 2013), pp. 157\u2013165. ACM Press, New York (2013). doi:10.1145\/2484239.2484264","DOI":"10.1145\/2484239.2484264"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-642-35476-2_16","volume-title":"Principles of Distributed Systems","author":"P. Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Halld\u00f3rsson, M.M., Korman, A.: On the impact of identifiers on local decision. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol.\u00a07702, pp. 224\u2013238. Springer, Heidelberg (2012)"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Hirvonen, J., Suomela, J.: Node Labels in Local Decision (2015). arXiv:1507.00909v1","DOI":"10.1007\/978-3-319-25258-2_3"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. In: Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011). IEEE Computer Society Press (2011). doi:10.1109\/FOCS.2011.17","DOI":"10.1109\/FOCS.2011.17"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Pelc, A., Peleg, D., P\u00e9rennes, S.: Assigning labels in an unknown anonymous network with a leader. Distributed Computing\u00a014(3), 163\u2013183 (2001). doi:10.1007\/PL00008935","DOI":"10.1007\/PL00008935"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distributed Computing\u00a016(2\u20133), 111\u2013120 (2003). doi:10.1007\/s00446-002-0073-5","DOI":"10.1007\/s00446-002-0073-5"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. Journal of the ACM 60(5)\u00a039, 1\u201323 (2013). doi:10.1145\/2528405","DOI":"10.1145\/2528405"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Hasemann, H., Hirvonen, J., Rybicki, J., Suomela, J.: Deterministic local algorithms, unique identifiers, and fractional graph colouring. Theoretical Computer Science (2014) (to appear). doi:10.1016\/j.tcs.2014.06.044","DOI":"10.1016\/j.tcs.2014.06.044"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Hella, L., J\u00e4rvisalo, M., Kuusisto, A., Laurinharju, J., Lempi\u00e4inen, T., Luosto, K., Suomela, J., Virtema, J.: Weak models of distributed computing, with connections to modal logic. Distributed Computing\u00a028(1), 31\u201353 (2015). doi:10.1007\/s00446-013-0202-3","DOI":"10.1007\/s00446-013-0202-3"},{"key":"3_CR19","unstructured":"Kranakis, E.: Symmetry and computability in anonymous networks: a brief survey. In: Proc. 3rd Colloquium on Structural Information and Communication Complexity (SIROCCO 1996), pp. 1\u201316. Carleton University Press (1997)"},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-540-87779-0_27","volume-title":"Distributed Computing","author":"C. Lenzen","year":"2008","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging linial\u2019s locality limit. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 394\u2013407. Springer, Heidelberg (2008)"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing\u00a021(1), 193\u2013201 (1992). doi:10.1137\/0221015","DOI":"10.1137\/0221015"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Mayer, A., Naor, M., Stockmeyer, L.: Local computations on static and dynamic graphs. In: Proc. 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS 1995), pp. 268\u2013278. IEEE (1995). doi:10.1109\/ISTCS.1995.377023","DOI":"10.1109\/ISTCS.1995.377023"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM Journal on Computing\u00a024(6), 1259\u20131277 (1995). doi:10.1137\/S0097539793254571","DOI":"10.1137\/S0097539793254571"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Norris, N.: Classifying anonymous networks: when can two networks compute the same set of vector-valued functions? In: Proc.1st Colloquium on Structural Information and Communication Complexity (SIROCCO 1994), pp. 83\u201398. Carleton University Press (1995)","DOI":"10.1515\/9780773591158-006"},{"key":"3_CR25","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley Publishing Company (1994)"},{"key":"3_CR26","series-title":"SIAM Monographs on Discrete Mathematics and Applications","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 Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Suomela, J.: Survey of local algorithms. ACM Computing Surveys 45(2)\u00a024:1\u201340 (2013). doi:10.1145\/2431211.2431223","DOI":"10.1145\/2431211.2431223"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Kameda, T.: Computing on anonymous networks: part I\u2014characterizing the solvable cases. IEEE Transactions on Parallel and Distributed Systems\u00a07(1), 69\u201389 (1996). doi:10.1109\/71.481599","DOI":"10.1109\/71.481599"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Kameda, T.: Leader election problem on networks in which processor identity numbers are not distinct. IEEE Transactions on Parallel and Distributed Systems\u00a010(9), 878\u2013887 (1999). doi:10.1109\/71.798313","DOI":"10.1109\/71.798313"}],"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-25258-2_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T13:38:52Z","timestamp":1692106732000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}