{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:46:53Z","timestamp":1742914013542,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":93,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642022494"},{"type":"electronic","value":"9783642022500"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02250-0_12","type":"book-chapter","created":{"date-parts":[[2009,11,17]],"date-time":"2009-11-17T11:17:06Z","timestamp":1258456626000},"page":"311-334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Time-Efficient Broadcast in Radio Networks"],"prefix":"10.1007","author":[{"given":"David","family":"Peleg","sequence":"first","affiliation":[]},{"given":"Tomasz","family":"Radzik","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,9]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0022-0000(91)90015-W","volume":"43","author":"N. Alon","year":"1991","unstructured":"Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Computer and System Sciences 43, (1991), 290\u2013298","journal-title":"J. Computer and System Sciences"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/0196-6774(92)90015-5","volume":"13","author":"N. Alon","year":"1992","unstructured":"Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: Single round simulation on radio networks. J. Algorithms 13, (1992), 188\u2013210","journal-title":"J. Algorithms"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Ambuhl, C., Clementi, A., Di Ianni, M., Lev-Tov, N., Monti, A., Peleg, D., Rossi, G., Silvestri, R.: Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks. In: Proc. 21st Symp. on Theoretical Aspects of Computer Science, LNCS 2996, 2004, 418\u2013427","DOI":"10.1007\/978-3-540-24749-4_37"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(85)90083-3","volume":"20","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: A new distributed depth-first-search algorithm. Information Processing Letters 20, (1985), 147\u2013150","journal-title":"Information Processing Letters"},{"key":"12_CR5","unstructured":"Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and light-weight spanners. Technical Report CS92-22, The Weizmann Institute, Rehovot, Israel, 1992"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/S0097539795279931","volume":"28","author":"B. Awerbuch","year":"1998","unstructured":"Awerbuch, B., Cidon, I., Kutten, S., Mansour, Y., Peleg, D.: Optimal broadcast with partial knowledge. SIAM J. Computing 28, (1998), 511\u2013524","journal-title":"SIAM J. Computing"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch, B., Goldreich, O., Peleg, D., Vainish, R.: A tradeoff between information and communication in broadcast protocols. J. ACM 37 (1990), 238\u2013256","journal-title":"J. ACM"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1002\/net.3230160405","volume":"16","author":"B. Awerbuch","year":"1986","unstructured":"Awerbuch, B., Even, S.: Reliable broadcast protocols in unreliable networks. Networks 16, (1986), 381\u2013396","journal-title":"Networks"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1109\/TCOM.1983.1095904","volume":"31","author":"B. Awerbuch","year":"1983","unstructured":"Awerbuch, B., Segall, A.: A reliable broadcast protocol. IEEE Trans. Communications 31, (1983), 896\u2013901","journal-title":"IEEE Trans. Communications"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0022-0000(92)90042-H","volume":"45","author":"R. Bar-Yehuda","year":"1992","unstructured":"Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time complexity of broadcast in radio networks: an exponential gap between determinism and randomization. J. Computer and System Sciences 45, (1992), 104\u2013126","journal-title":"J. Computer and System Sciences"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/0222055","volume":"22","author":"R. Bar-Yehuda","year":"1993","unstructured":"Bar-Yehuda, R., Israeli, A., Itai, A.: Multiple communication in multihop radio networks. SIAM J. Computing 22, (1993), 875\u2013887","journal-title":"SIAM J. Computing"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1109\/90.811446","volume":"7","author":"S. Basagni","year":"1999","unstructured":"Basagni, S., Bruschi, D., Chlamtac, I.: A mobility-transparent deterministic broadcast mechanism for ad hoc networks. IEEE\/ACM Trans. Networking 7, (1999), 799\u2013807","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"12_CR13","unstructured":"Basagni, S., Myers, A. D., Syrotiuk, V. R.: Mobility-independent flooding for real-time multimedia applications in ad hoc networks. In: Proc. IEEE Emerging Technologies Symp. on Wireless Communications and Systems, 1999, 20.1\u201320.5"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Cooper, C., Hu, Z.: Energy efficient randomized communication in unknown ad hoc networks. In: Proc. 19th ACM Symp. on Parallel Algorithms and Architectures, 2007, 250\u2013259","DOI":"10.1145\/1248377.1248419"},{"key":"12_CR15","volume-title":"Data Networks.","author":"D. Bertsekas","year":"1987","unstructured":"Bertsekas, D., Gallager, R.: Data Networks. Prantice Hall, New Jersey, 1987"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Bhandari, V., Vaidya, N. H.: On reliable broadcast in a radio network. In: Proc. 24th ACM Symp. on Principles of Distributed Computing, 2005, 138\u2013147","DOI":"10.1145\/1073814.1073841"},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Bhandari, V., Vaidya, N. H.: Reliable broadcast in wireless networks with probabilistic failures. In: Proc. 26th Joint Conf. of IEEE Computer and Communication Societies (INFOCOM), 2007, 715\u2013723","DOI":"10.1109\/INFCOM.2007.89"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s004460050030","volume":"10","author":"D. Bruschi","year":"1997","unstructured":"Bruschi, D., M. Del Pinto. Lower bounds for the broadcast problem in mobile radio networks. Distributed Computing 10, (1997), 129\u2013135","journal-title":"Distributed Computing"},{"key":"12_CR19","unstructured":"G. C\u01celinescu, Li, X. Y., Frieder, O., Wan, P. J.: Minimum-energy broadcast routing in static ad hoc wireless networks. In: Proc. 20th Joint Conf. of IEEE Computer and Communications Societies (INFOCOM), 2001, 1162\u20131171"},{"key":"12_CR20","unstructured":"Chandra, R., Ramasubramanian, V., Birman, K. P.: Anonymous gossip: improving multicast reliability in mobile ad-hoc networks. In: Proc. 21st Conf. on Distributed Computing Systems, 2001, 275\u2013283"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/90.282605","volume":"2","author":"I. Chlamtac","year":"1994","unstructured":"Chlamtac, I., A. Farag\u00f3. Making transmission schedule immune to topology changes in multi-hop packet radio networks. IEEE\/ACM Trans. Networking 2, (1994), 23\u201329","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1109\/90.650140","volume":"5","author":"I. Chlamtac","year":"1997","unstructured":"Chlamtac, I., Farag\u00f3, A., Zhang, H.: Time-spread multiple access (TSMA) protocols for multihop mobile radio networks. IEEE\/ACM Trans. Networking 5, (1997), 804\u2013812","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"1240","DOI":"10.1109\/TCOM.1985.1096245","volume":"33","author":"I. Chlamtac","year":"1985","unstructured":"Chlamtac, I., Kutten, S.: On broadcasting in radio networks \u2013 problem analysis and protocol design. IEEE Trans. Communications 33, (1985), 1240\u20131246","journal-title":"IEEE Trans. Communications"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1109\/TC.1987.1676861","volume":"36","author":"I. Chlamtac","year":"1987","unstructured":"Chlamtac, I., Kutten, S.: Tree-based broadcasting in multihop radio networks, IEEE Trans. Computers 36, (1987), 1209\u20131223","journal-title":"IEEE Trans. Computers"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1109\/26.79285","volume":"39","author":"I. Chlamtac","year":"1991","unstructured":"Chlamtac, I., Weinstein, O.: The wave expansion approach to broadcasting in multihop radio networks. IEEE Trans. Communications 39, (1991), 426\u2013433","journal-title":"IEEE Trans. Communications"},{"key":"12_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s446-002-8028-1","volume":"15","author":"B. S. Chlebus","year":"2002","unstructured":"Chlebus, B. S., L. G\u00b8asieniec, Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in unknown radio networks. Distributed Computing 15, (2002), 27\u201338","journal-title":"Distributed Computing"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Chlebus, B. S., Gasieniec, L., Kowalski, D. R., Radzik, T.: On the wake-up problem in radio networks. In: Proc. 32nd Int. Colloq. on Automata, Languages and Programming, LNCS 3580, 2005, 347\u2013359","DOI":"10.1007\/11523468_29"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Chlebus, B. S., L. G\u00b8asieniec, Ostlin, A., Robson, J. M.: Deterministic radio broadcasting. In: Proc. 27th Int. Colloq. on Automata, Languages and Programming 2000, LNCS 1853, 717\u2013728","DOI":"10.1007\/3-540-45022-X_60"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Chlebus, B. S., Kowalski, D. R.: A better wake-up in radio networks. In: Proc. 23rd ACN Symp. on Principles of Distributed Computing, 2004, 266\u2013274","DOI":"10.1145\/1011767.1011806"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Chlebus, B. S., Kowalski, D. R.: Almost optimal explicit selectors. In: Proc. 15th Symp. on Fundamentals of Computation Theory, LNCS 3623, 2005, 270\u2013280","DOI":"10.1007\/11537311_24"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"Chlebus, B. S., Rokicki, M.: Asynchronous broadcast in radio networks, In: Proc. 11th Colloq. on Structural Information and Communication Complexity, 2004, LNCS 3104, 57\u201368","DOI":"10.1007\/978-3-540-27796-5_6"},{"key":"12_CR32","unstructured":"Chrobak, M., G\u00b8asieniec, L., Kowalski, D. R.: The wake-up problem in multi-hop radio networks. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms 2004, 985\u2013993"},{"key":"12_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0196-6774(02)00004-4","volume":"43","author":"M. Chrobak","year":"2002","unstructured":"Chrobak, M., G\u00b8asieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. J. Algorithms 43, (2002), 177-189","journal-title":"J. Algorithms"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Manne, F., Xin, Q.: Faster centralized communication in radio networks. In: Proc. 17th Symp. on Algorithms and Computation, LNCS 4288, 2006, 339\u2013348","DOI":"10.1007\/11940128_35"},{"key":"12_CR35","unstructured":"Clementi, A. E. F., Huiban, G., Penna, P., Rossi, G., Verhoeven, Y. C.: Some recent theoretical advances and open questions on energy consumption in ad-hoc wireless networks. In: Proc. 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, 23\u201338, 2002"},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Clementi, A. E. F., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the complexity of computing minimum energy consumption broadcast subgraphs. In: Proc. 18th Symp. on Theoretical Aspects of Computer Science, LNCS 2010, 121\u2013131, 2001","DOI":"10.1007\/3-540-44693-1_11"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Clementi, A. E. F., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms, 2001, 709\u2013718","DOI":"10.1145\/383962.384040"},{"key":"12_CR38","doi-asserted-by":"crossref","unstructured":"Clementi, A. E. F., Crescenzi, P., Monti, A., Penna, P., Silvestri, R.: On computing ad-hoc selective families. In: Proc. 4th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, LNCS 2129, 2001, 211\u2013222","DOI":"10.1007\/3-540-44666-4_24"},{"key":"12_CR39","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00851-4","volume":"302","author":"A. E. F. Clementi","year":"2003","unstructured":"Clementi, A. E. F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theoretical Computer Science 302, (2003), 337\u2013364","journal-title":"Theoretical Computer Science"},{"key":"12_CR40","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.jpdc.2003.09.002","volume":"64","author":"A. E. F. Clementi","year":"2004","unstructured":"Clementi, A. E. F., Monti, A., Silvestri, R.: Round robin is optimal for fault-tolerant broadcasting on wireless networks. J. Parallel and Distributed Computing 64, (2004), 89\u201396","journal-title":"J. Parallel and Distributed Computing"},{"key":"12_CR41","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/S0895480295292934","volume":"11","author":"A. Czumaj","year":"1998","unstructured":"Czumaj, A., G\u00b8asieniec, L., Pelc, A.: Time and cost trade-offs in gossiping. SIAM J. Discrete Mathematics 11, (1998), 400\u2013413","journal-title":"SIAM J. Discrete Mathematics"},{"key":"12_CR42","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jalgor.2004.08.001","volume":"60","author":"A. Czumaj","year":"2006","unstructured":"Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. J. Algorithms 60, (2006), 115\u2013143","journal-title":"J. Algorithms"},{"key":"12_CR43","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.jda.2006.07.001","volume":"5","author":"A. Dessmark","year":"2007","unstructured":"Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. J. Discrete Algorithms 5, (2007), 187\u2013201","journal-title":"J. Discrete Algorithms"},{"key":"12_CR44","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1002\/net.10016","volume":"39","author":"A. Dessmark","year":"2002","unstructured":"Dessmark, A., Pelc, A.: Deterministic radio broadcasting at low cost. Networks 39, (2002), 88\u201397","journal-title":"Networks"},{"key":"12_CR45","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0020-0190(00)00178-2","volume":"79","author":"G. De Marco","year":"2001","unstructured":"De Marco, G., Pelc, A.: Faster broadcasting in unknown radio networks. Information Processing Letters 79 (2001) 53\u201356","journal-title":"Information Processing Letters"},{"key":"12_CR46","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/S0304-3975(01)00256-0","volume":"287","author":"K. Diks","year":"2002","unstructured":"Diks, K., Kranakis, E., Krizanc, D., Pelc, A.: The impact of knowledge on broadcasting time in linear radio networks. Theoretical Computer Science 287, (2002), 449\u2013471","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"12_CR47","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.jalgor.2003.11.004","volume":"52","author":"M. Elkin","year":"2004","unstructured":"Elkin, M., Kortsarz, G.: Logarithmic inapproximability of the radio broadcast problem. J. Algorithms 52(1), (2004), 8\u201325","journal-title":"J. Algorithms"},{"key":"12_CR48","doi-asserted-by":"crossref","unstructured":"Elkin, M., Kortsarz, G.: Polylogarithmic inapproximability of the radio broadcast problem. In: Proc. 7th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004, LNCS 3122, 105\u2013116","DOI":"10.1007\/978-3-540-27821-4_10"},{"key":"12_CR49","unstructured":"Elkin, M., Kortsarz, G.: Improved schedule for radio broadcast. In: Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, 2005, 222\u2013231."},{"key":"12_CR50","doi-asserted-by":"crossref","unstructured":"Emek, Y., L. G\u00b8asieniec, Kantor, E., Pelc, A., Peleg, D., Su, C.: Broadcasting in UDG radio networks with unknown topology. In: Proc. ACM Symp. on Principles of Distributed Computing, 2007, 195\u2013204","DOI":"10.1145\/1281100.1281130"},{"key":"12_CR51","doi-asserted-by":"crossref","unstructured":"Emek, Y., Kantor, E., Peleg, D.: On the effect of the deployment setting on broadcasting in euclidean radio networks. In: Proc. ACM Symp. on Principles of Distributed Computing, 2008, 223\u2013232","DOI":"10.1145\/1400751.1400782"},{"key":"12_CR52","unstructured":"Ephremides, A., Nguyen, G. D., Wieselthier, J. E.: On the construction of energy-efficient broadcast and multicast trees in wireless networks. In: Proc. 19th Joint Conf. of IEEE Computer and Communications Societies (INFOCOM), 585\u2013594, 2000"},{"key":"12_CR53","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/net.3230090404","volume":"9","author":"A. M. Farley","year":"1979","unstructured":"Farley, A. M.: Minimal broadcast networks. Networks 9, (1979), 313\u2013332","journal-title":"Networks"},{"key":"12_CR54","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0012-365X(79)90022-0","volume":"25","author":"A. M. Farley","year":"1979","unstructured":"Farley, A. M., Hedetniemi, S. T., Mitchell, S., Proskurowski, A.: Minimum broadcast graphs. Discrete Mathematics 25, (1979), 189\u2013193","journal-title":"Discrete Mathematics"},{"key":"12_CR55","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1002\/rsa.3240010406","volume":"1","author":"U. Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: The complexity of randomized broadcast. J. on Random Structures & Algorithms 1, (1990), 447\u2013460","journal-title":"J. on Random Structures & Algorithms"},{"key":"12_CR56","doi-asserted-by":"crossref","unstructured":"Fernandez, A., Mosteiro, M. A., Thraves, C.: Deterministic communication in the weak sensor model. In: Proc. 11th Conf. On Principles Of Distributed Systems, LNCS 4878, 2007, 119\u2013131","DOI":"10.1007\/978-3-540-77096-1_9"},{"key":"12_CR57","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","volume":"53","author":"P. Fraigniaud","year":"1994","unstructured":"Fraigniaud, P., Lazard, E.: Methods and problems of communication in usual networks. Discrete Applied Mathematics 53, (1994), 79\u2013133","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR58","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0196-6774(02)00292-4","volume":"46","author":"I. Gaber","year":"2003","unstructured":"Gaber, I., Mansour, Y.: Centralized broadcast in multihop radio networks. J. Algorithms 46, (2003), 1\u201320","journal-title":"J. Algorithms"},{"key":"12_CR59","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1002\/net.1022","volume":"38","author":"L. Gargano","year":"2001","unstructured":"Gargano, L., Pelc, A., P\u00e9rennes, S., Vaccaro, U., Efficient communication in unknown networks, Networks 38, (2001), 39\u201349","journal-title":"Networks"},{"key":"12_CR60","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s00453-006-1212-3","volume":"47","author":"L. G\u00b8asieniec","year":"2007","unstructured":"G\u00b8asieniec, L., Pagourtzis, A., Potapov, I., Radzik, T.: Deterministic communication in radio networks with large labels. Algorithmica 47, (2007), 97\u2013117","journal-title":"Algorithmica"},{"key":"12_CR61","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/S0895480100376022","volume":"14","author":"L. G\u00b8asieniec","year":"2001","unstructured":"G\u00b8asieniec, L., Pelc, A., Peleg, D.: The wakeup problem in synchronous broadcast systems. SIAM J. Discrete Mathematics 14, (2001), 207\u2013222","journal-title":"SIAM J. Discrete Mathematics"},{"key":"12_CR62","doi-asserted-by":"crossref","unstructured":"G\u00b8asieniec, L., Peleg, D., Xin, Q.: Faster communication in known topology radio networks. In: Proc. 24th ACM Symp. on Principles Of Distributed Computing, 2005, 129\u2013137","DOI":"10.1145\/1073814.1073840"},{"key":"12_CR63","doi-asserted-by":"crossref","unstructured":"G\u00b8asieniec, L., Kantor, E., Kowalski, D. R., Peleg, D., Su, C.: Energy and time efficient broadcasting in known topology radio networks. In: Proc. 21st Symp. on Distributed Computing, 2007, LNCS 4731, 253\u2013267","DOI":"10.1007\/978-3-540-75142-7_21"},{"key":"12_CR64","doi-asserted-by":"crossref","unstructured":"G\u00b8asieniec, L., Radzik, T., Xin, Q.: Faster deterministic gossiping in directed ad hoc radio networks. In: Proc. 9th Scandinavian Workshop on Algorithm Theory, LNCS 3111, 2004, 397\u2013407","DOI":"10.1007\/978-3-540-27810-8_34"},{"key":"12_CR65","doi-asserted-by":"crossref","unstructured":"Gandhi, R., Parthasarathy, S., Mishra, A.: Minimizing broadcast latency and redundancy in ad hoc networks. In: Proc. 4th ACM Symp. on Mobile ad hoc networking and computing, 2003, 222\u2013232.","DOI":"10.1145\/778415.778442"},{"key":"12_CR66","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1109\/TNET.2006.876186","volume":"14","author":"Z. J. Haas","year":"2006","unstructured":"Haas, Z. J., Halpern, J. Y., Li, L.: Gossip-based ad hoc routing. IEEE\/ACM Trans. Networking 14, (2006), 479\u2013491","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"12_CR67","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"S. Hedetniemi","year":"1988","unstructured":"Hedetniemi, S., Hedetniemi, S., Liestman, A.: A survey of gossiping and broadcasting in communication networks. Networks 18, (1988), 319\u2013349","journal-title":"Networks"},{"key":"12_CR68","first-page":"179","volume":"16","author":"P. A. Humblet","year":"1989","unstructured":"Humblet, P. A., Soloway, S. R.: Topology broadcast algorithms. Computer Networks 16, (1989), 179\u2013186","journal-title":"Computer Networks"},{"key":"12_CR69","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0166-218X(94)00053-G","volume":"60","author":"F. K. Hwang","year":"1995","unstructured":"Hwang, F. K.: The time complexity of deterministic broadcast radio networks. Discrete Applied Mathematics 60, (1995), 219\u2013222","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR70","unstructured":"Indyk, P.: Explicit constructions of selectors and related combinatorial structures, with applications. In: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002, 697\u2013704"},{"key":"12_CR71","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Stachowiak, G.: Probabilistic algorithms for the wakeup problem in single-hop radio networks. In: Proc. 13th Int. Symp. on Algorithms and Computation (ISAAC 2002), LNCS 2518, 535 \u2013 549","DOI":"10.1007\/3-540-36136-7_47"},{"key":"12_CR72","unstructured":"Kesselman, A., Kowalski, D. R.: Fast distributed algorithm for convergecast in ad hoc geometric radio networks. In: Proc. 2nd Conf. on Wireless on Demand Network Systems and Service, 2005, 119\u2013124"},{"key":"12_CR73","doi-asserted-by":"crossref","unstructured":"C.-Koo, Y.: Broadcast in radio networks tolerating byzantine adversarial behavior. In: Proc. 23rd ACM Symp. on Principles of Distributed Computing, 2004, 275\u2013282","DOI":"10.1145\/1011767.1011807"},{"key":"12_CR74","doi-asserted-by":"crossref","unstructured":"C.-Koo, Y., Bhandari, V., Katz, J., Vaidya, N. H.: Reliable broadcast in radio networks: the bounded collision case. In: Proc. 25th ACM Symp. on Principles of Distributed Computing, 2006, 258\u2013264","DOI":"10.1145\/1146381.1146420"},{"key":"12_CR75","unstructured":"Kothapalli, K., Onus, M., Richa, A., Scheideler, C.: Efficient broadcasting and gathering in wireless ad hoc networks. In: Proc. IEEE Symp. on Parallel Architectures, Algorithms and Networks, 2005, 346\u2013351"},{"key":"12_CR76","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/S089548010342464X","volume":"18","author":"D. R. Kowalski","year":"2004","unstructured":"Kowalski, D. R., Pelc, A.: Faster deterministic broadcasting in ad hoc radio networks. SIAM J. Discrete Mathematics 18, (2004), 332\u2013346","journal-title":"SIAM J. Discrete Mathematics"},{"key":"12_CR77","doi-asserted-by":"crossref","unstructured":"Kowalski, D. R., Pelc, A.: Centralized deterministic broadcasting in undirected multi-hop radio networks. In: Proc. 7th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004, LNCS 3122, 171\u2013182","DOI":"10.1007\/978-3-540-27821-4_16"},{"key":"12_CR78","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1137\/S0097539702419339","volume":"33","author":"D. R. Kowalski","year":"2004","unstructured":"Kowalski, D. R., Pelc, A.: Time of deterministic broadcasting in radio networks with local knowledge, SIAM J. Computing 33, (2004), 870\u2013891","journal-title":"SIAM J. Computing"},{"key":"12_CR79","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00446-005-0126-7","volume":"18","author":"D. R. Kowalski","year":"2005","unstructured":"Kowalski, D. R., Pelc, A.: Broadcasting in undirected ad hoc radio networks. Distributed Computing 18, (2005), 43\u201357","journal-title":"Distributed Computing"},{"key":"12_CR80","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/j.tcs.2004.04.017","volume":"333","author":"D. R. Kowalski","year":"2005","unstructured":"Kowalski, D. R., Pelc, A.: Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism. Theoretical Computer Science 333, (2005), 355\u2013371","journal-title":"Theoretical Computer Science"},{"key":"12_CR81","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s00446-006-0007-8","volume":"19","author":"D. R. Kowalski","year":"2007","unstructured":"Kowalski, D. R., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distributed Computing 19, (2007), 185\u2013195","journal-title":"Distributed Computing"},{"key":"12_CR82","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jagm.2000.1147","volume":"39","author":"E. Kranakis","year":"2001","unstructured":"Kranakis, E., Krizanc, D., Pelc, A.: Fault-tolerant broadcasting in radio networks. J. Algorithms 39, (2001), 47\u201367","journal-title":"J. Algorithms"},{"key":"12_CR83","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1137\/S0097539794279109","volume":"27","author":"E. Kushilevitz","year":"1998","unstructured":"Kushilevitz, E., Mansour, Y.: An \u03a9(D log (N\/D)) lower bound for broadcast in radio networks. SIAM J. Computing 27, (1998), 702\u2013712","journal-title":"SIAM J. Computing"},{"key":"12_CR84","doi-asserted-by":"crossref","unstructured":"Pagani, E., Rossi, G. P.: Reliable broadcast in mobile multihop radio networks. In: Proc. 3rd ACM\/IEEE Conf. on Mobile Computing and Networking, 1997, 34\u201342","DOI":"10.1145\/262116.262125"},{"key":"12_CR85","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<143::AID-NET3>3.0.CO;2-N","volume":"28","author":"A. Pelc","year":"1996","unstructured":"Pelc, A.: Fault-tolerant broadcasting and gossiping in communication networks. Networks 28, (1996), 143\u2013156","journal-title":"Networks"},{"key":"12_CR86","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.ipl.2004.10.007","volume":"93","author":"A. Pelc","year":"2005","unstructured":"Pelc, A., Peleg, D.: Broadcasting with locally bounded Byzantine faults. Information Processing Letters 93, (2005), 109\u2013115","journal-title":"Information Processing Letters"},{"key":"12_CR87","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000","DOI":"10.1137\/1.9780898719772"},{"key":"12_CR88","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0166-218X(94)90193-7","volume":"53","author":"K. Ravishankar","year":"1994","unstructured":"Ravishankar, K., Singh, S.: Broadcasting on [0,L]. Discrete Applied Mathematics 53, (1994), 299\u2013319","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR89","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/TIT.1983.1056620","volume":"29","author":"A. Segall","year":"1983","unstructured":"Segall, A.: Distributed network protocols. IEEE Trans. Information Theory 29, (1983), 23\u201335","journal-title":"IEEE Trans. Information Theory"},{"key":"12_CR90","unstructured":"Sen, A., Huson, M. L.: A new model for scheduling packet radio networks. In: Proc. 15th Joint Conf. of IEEE Computer and Communication Societies (INFOCOM), 1996, 1116\u20131124"},{"key":"12_CR91","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1109\/TPDS.2006.53","volume":"17","author":"W.-Z. Song","year":"2006","unstructured":"Song, W.-Z., Li, X.-Y., Frieder, O., Wang, W.: Localized topology control for unicast and broadcast in wireless ad hoc networks. IEEE Trans. Parallel & Distributed Systems 17, (2006), 321\u2013334","journal-title":"IEEE Trans. Parallel & Distributed Systems"},{"key":"12_CR92","unstructured":"Toh, C. K.: Ad Hoc Mobile Wireless Networks. Prantice Hall, 2002"},{"key":"12_CR93","doi-asserted-by":"crossref","unstructured":"Williams, B., Camp, T.: Comparison of broadcasting techniques for mobile ad hoc networks. In: Proc. 3rd ACM Symp. on Mobile Ad Hoc Networking and Computing, 2002, 194\u2013205","DOI":"10.1145\/513800.513825"}],"container-title":["Texts in Theoretical Computer Science. An EATCS Series","Graphs and Algorithms in Communication Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02250-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T22:21:27Z","timestamp":1675894887000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02250-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022494","9783642022500"],"references-count":93,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02250-0_12","relation":{},"ISSN":["1862-4499"],"issn-type":[{"type":"print","value":"1862-4499"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"9 November 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}