{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:13Z","timestamp":1770994093872,"version":"3.50.1"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030868376","type":"print"},{"value":"9783030868383","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-86838-3_29","type":"book-chapter","created":{"date-parts":[[2021,9,19]],"date-time":"2021-09-19T22:05:30Z","timestamp":1632089130000},"page":"374-387","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Labeling Schemes for Deterministic Radio Multi-broadcast"],"prefix":"10.1007","author":[{"given":"Colin","family":"Krisko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8231-3697","authenticated-orcid":false,"given":"Avery","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Albertson, M.O., Collins, K.L.: Symmetry breaking in graphs. Electron. J. Comb. 3(1) (1996). http:\/\/www.combinatorics.org\/Volume_3\/Abstracts\/v3i1r18.html","DOI":"10.37236\/1242"},{"key":"29_CR2","doi-asserted-by":"publisher","unstructured":"Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43(2), 290\u2013298 (1991). https:\/\/doi.org\/10.1016\/0022-0000(91)90015-W","DOI":"10.1016\/0022-0000(91)90015-W"},{"key":"29_CR3","doi-asserted-by":"publisher","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv. 50(2), 19:1\u201319:34 (2017). https:\/\/doi.org\/10.1145\/3056461","DOI":"10.1145\/3056461"},{"key":"29_CR4","unstructured":"Bu, G., Lotker, Z., Potop-Butucaru, M., Rabie, M.: Lower and upper bounds for deterministic convergecast with labeling schemes. Research report, Sorbonne Universit\u00e9, May 2020. https:\/\/hal.archives-ouvertes.fr\/hal-02650472"},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-030-67087-0_10","volume-title":"Networked Systems","author":"G Bu","year":"2021","unstructured":"Bu, G., Potop-Butucaru, M., Rabie, M.: Wireless broadcast with short labels. In: Georgiou, C., Majumdar, R. (eds.) NETYS 2020. LNCS, vol. 12129, pp. 146\u2013169. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-67087-0_10"},{"key":"29_CR6","doi-asserted-by":"publisher","unstructured":"Chlamtac, I.: The wave expansion approach to broadcasting in multihop radio networks. IEEE Trans. Commun. 39(3), 426\u2013433 (1991). https:\/\/doi.org\/10.1109\/26.79285","DOI":"10.1109\/26.79285"},{"key":"29_CR7","doi-asserted-by":"publisher","unstructured":"Chlamtac, I., Kutten, S.: On broadcasting in radio networks-problem analysis and protocol design. IEEE Trans. Commun. 33(12), 1240\u20131246 (1985). https:\/\/doi.org\/10.1109\/TCOM.1985.1096245","DOI":"10.1109\/TCOM.1985.1096245"},{"key":"29_CR8","doi-asserted-by":"publisher","unstructured":"Chlebus, B.S., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distrib. Comput. 15(1), 27\u201338 (2002). https:\/\/doi.org\/10.1007\/s446-002-8028-1","DOI":"10.1007\/s446-002-8028-1"},{"key":"29_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/3-540-45022-X_60","volume-title":"Automata, Languages and Programming","author":"BS Chlebus","year":"2000","unstructured":"Chlebus, B.S., Gasieniec, L., \u00d6stlin, A., Robson, J.M.: Deterministic radio broadcasting. In: Montanari, U., Rolim, J.D.P., Welzl, E. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 717\u2013729. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45022-X_60"},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/978-3-642-22012-8_49","volume-title":"Automata, Languages and Programming","author":"BS Chlebus","year":"2011","unstructured":"Chlebus, B.S., Kowalski, D.R., Pelc, A., Rokicki, M.A.: Efficient distributed communication in ad-hoc radio networks. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 613\u2013624. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22012-8_49"},{"key":"29_CR11","doi-asserted-by":"publisher","unstructured":"Chlebus, B.S., Kowalski, D.R., Radzik, T.: Many-to-many communication in radio networks. Algorithmica 54(1), 118\u2013139 (2009). https:\/\/doi.org\/10.1007\/s00453-007-9123-5","DOI":"10.1007\/s00453-007-9123-5"},{"key":"29_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/3-540-45465-9_33","volume-title":"Automata, Languages and Programming","author":"M Christersson","year":"2002","unstructured":"Christersson, M., G\u0105sieniec, L., Lingas, A.: Gossiping with bounded size messages in ad hoc radio networks. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 377\u2013389. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45465-9_33"},{"key":"29_CR13","doi-asserted-by":"publisher","unstructured":"Chrobak, M., Gasieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. J. Algorithms 43(2), 177\u2013189 (2002). https:\/\/doi.org\/10.1016\/S0196-6774(02)00004-4","DOI":"10.1016\/S0196-6774(02)00004-4"},{"key":"29_CR14","doi-asserted-by":"publisher","unstructured":"Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed multi-broadcast in unknown radio networks. In: Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, PODC 2001, pp. 255\u2013264. Association for Computing Machinery, New York (2001). https:\/\/doi.org\/10.1145\/383962.384040","DOI":"10.1145\/383962.384040"},{"key":"29_CR15","doi-asserted-by":"publisher","unstructured":"Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theoret. Comput. Sci. 302(1\u20133), 337\u2013364 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00851-4","DOI":"10.1016\/S0304-3975(02)00851-4"},{"key":"29_CR16","unstructured":"Dobrev, S., Kralovic, R., Kralovic, R., et al.: Computing with advice: when knowledge helps. Bull. EATCS 2(110) (2013)"},{"key":"29_CR17","doi-asserted-by":"publisher","unstructured":"Elkin, M., Kortsarz, G.: An improved algorithm for radio broadcast. ACM Trans. Algorithms 3(1), 8:1\u20138:21 (2007). https:\/\/doi.org\/10.1145\/1219944.1219954","DOI":"10.1145\/1219944.1219954"},{"key":"29_CR18","doi-asserted-by":"publisher","unstructured":"Ellen, F., Gilbert, S.: Constant-length labelling schemes for faster deterministic radio broadcast. In: SPAA 2020: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 213\u2013222 (2020). https:\/\/doi.org\/10.1145\/3350755.3400238","DOI":"10.1145\/3350755.3400238"},{"key":"29_CR19","unstructured":"Ellen, F., Gorain, B., Miller, A., Pelc, A.: Constant-length labeling schemes for deterministic radio broadcast. CoRR abs\/1710.03178 (2017). http:\/\/arxiv.org\/abs\/1710.03178"},{"key":"29_CR20","doi-asserted-by":"publisher","unstructured":"Ellen, F., Gorain, B., Miller, A., Pelc, A.: Constant-length labeling schemes for deterministic radio broadcast. In: The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, pp. 171\u2013178 (2019). https:\/\/doi.org\/10.1145\/3323165.3323194","DOI":"10.1145\/3323165.3323194"},{"key":"29_CR21","unstructured":"Feuilloley, L.: Introduction to local certification. CoRR abs\/1910.12747 (2019). http:\/\/arxiv.org\/abs\/1910.12747"},{"key":"29_CR22","doi-asserted-by":"publisher","unstructured":"Gaber, I., Mansour, Y.: Centralized broadcast in multihop radio networks. J. Algorithms 46(1), 1\u201320 (2003). https:\/\/doi.org\/10.1016\/S0196-6774(02)00292-4","DOI":"10.1016\/S0196-6774(02)00292-4"},{"key":"29_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-11476-2_2","volume-title":"Structural Information and Communication Complexity","author":"L G\u0105sieniec","year":"2010","unstructured":"G\u0105sieniec, L.: On efficient gossiping in radio networks. In: Kutten, S., \u017derovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 2\u201314. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11476-2_2"},{"key":"29_CR24","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Kranakis, E., Pelc, A., Xin, Q.: Deterministic M2M multicast in radio networks. Theoret. Comput. Sci. 362(1\u20133), 196\u2013206 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2006.06.017","DOI":"10.1016\/j.tcs.2006.06.017"},{"key":"29_CR25","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Lingas, A.: On adaptive deterministic gossiping in ad hoc radio networks. Inf. Process. Lett. 83(2), 89\u201393 (2002). https:\/\/doi.org\/10.1016\/S0020-0190(01)00312-X","DOI":"10.1016\/S0020-0190(01)00312-X"},{"key":"29_CR26","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Pagourtzis, A., Potapov, I., Radzik, T.: Deterministic communication in radio networks with large labels. Algorithmica 47(1), 97\u2013117 (2007). https:\/\/doi.org\/10.1007\/s00453-006-1212-3","DOI":"10.1007\/s00453-006-1212-3"},{"key":"29_CR27","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. Distributed Comput. 19(4), 289\u2013300 (2007). https:\/\/doi.org\/10.1007\/s00446-006-0011-z","DOI":"10.1007\/s00446-006-0011-z"},{"key":"29_CR28","series-title":"IFIP \u2014 The International Federation for Information Processing","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-0-387-35608-2_17","volume-title":"Foundations of Information Technology in the Era of Network and Mobile Computing","author":"L G\u0105sieniec","year":"2002","unstructured":"G\u0105sieniec, L., Potapov, I.: Gossiping with unit messages in known radio networks. In: Baeza-Yates, R., Montanari, U., Santoro, N. (eds.) Foundations of Information Technology in the Era of Network and Mobile Computing. ITIFIP, vol. 96, pp. 193\u2013205. Springer, Boston, MA (2002). https:\/\/doi.org\/10.1007\/978-0-387-35608-2_17"},{"key":"29_CR29","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Potapov, I., Xin, Q.: Time efficient centralized gossiping in radio networks. Theoret. Comput. Sci. 383(1), 45\u201358 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.03.059","DOI":"10.1016\/j.tcs.2007.03.059"},{"key":"29_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-319-72050-0_3","volume-title":"Structural Information and Communication Complexity","author":"B Gorain","year":"2017","unstructured":"Gorain, B., Pelc, A.: Short labeling schemes for topology recognition in wireless tree networks. In: Das, S., Tixeuil, S. (eds.) SIROCCO 2017. LNCS, vol. 10641, pp. 37\u201352. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-72050-0_3"},{"key":"29_CR31","doi-asserted-by":"publisher","unstructured":"Gorain, B., Pelc, A.: Finding the size and the diameter of a radio network using short labels. Theoret. Comput. Sci. (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.02.004","DOI":"10.1016\/j.tcs.2021.02.004"},{"key":"29_CR32","unstructured":"Ilcinkas, D.: Structural information in distributed computing. Ph.D. thesis, Universit\u00e9 de Bordeaux (2019). https:\/\/tel.archives-ouvertes.fr\/tel-03099722"},{"key":"29_CR33","doi-asserted-by":"publisher","unstructured":"Ilcinkas, D., Kowalski, D.R., Pelc, A.: Fast radio broadcasting with advice. Theoret. Comput. Sci. 411(14\u201315), 1544\u20131557 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.01.004","DOI":"10.1016\/j.tcs.2010.01.004"},{"key":"29_CR34","doi-asserted-by":"publisher","unstructured":"Kowalski, D.R., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19(3), 185\u2013195 (2007). https:\/\/doi.org\/10.1007\/s00446-006-0007-8","DOI":"10.1007\/s00446-006-0007-8"},{"key":"29_CR35","doi-asserted-by":"publisher","unstructured":"Levin, L., Kowalski, D.R., Segal, M.: Message and time efficient multi-broadcast schemes. Theoret. Comput. Sci. 569, 13\u201323 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.12.006","DOI":"10.1016\/j.tcs.2014.12.006"},{"key":"29_CR36","doi-asserted-by":"crossref","unstructured":"Tymoczko, J.: Distinguishing numbers for graphs and groups. Electron. J. Comb. 11(1) (2004). http:\/\/www.combinatorics.org\/Volume_11\/Abstracts\/v11i1r63.html","DOI":"10.37236\/1816"}],"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-030-86838-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T20:04:09Z","timestamp":1702065849000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86838-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030868376","9783030868383"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86838-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 June 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"47","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair and OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held online due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}