{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:29:59Z","timestamp":1725564599614},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_47","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T19:01:54Z","timestamp":1283972514000},"page":"534-546","source":"Crossref","is-referenced-by-count":3,"title":["An Information Theoretic Lower Bound for Broadcasting in Radio Networks"],"prefix":"10.1007","author":[{"given":"Carlos","family":"Brito","sequence":"first","affiliation":[]},{"given":"Eli","family":"Gafni","sequence":"additional","affiliation":[]},{"given":"Shailesh","family":"Vaya","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"47_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. Journal of Computer Science and System Sciences\u00a043, 290\u2013298 (1991)","journal-title":"Journal of Computer Science and System Sciences"},{"key":"47_CR2","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\u00a020, 147\u2013150 (1985)","journal-title":"Information Processing Letters"},{"key":"47_CR3","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. Journal of Computer and System Sciences\u00a045, 104\u2013126 (1992)","journal-title":"Journal of Computer and System Sciences"},{"key":"47_CR4","unstructured":"Pelc, A.: Personal communication (November 2002)"},{"key":"47_CR5","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Rytter, W.: Broadcasting Algorithms in Radio Networks with Unknown Topology. To appear in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA (2003)","DOI":"10.1109\/SFCS.2003.1238222"},{"key":"47_CR6","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s004460050030","volume":"10","author":"B. Bruschi","year":"1997","unstructured":"Bruschi, B., Del Pinto, M.: Lower bounds for the broadcast problem in mobile radio networks. Distr. Comp.\u00a010, 129\u2013135 (1997)","journal-title":"Distr. Comp."},{"key":"47_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/90.282605","volume":"2","author":"I. Chlamtac","year":"1994","unstructured":"Chlamtac, I., Farago, A.: Making transmission schedule immune to topology changes in multi-hop packet radio networks. IEEE\/ACM Trans. on Networking\u00a02, 23\u201329 (1994)","journal-title":"IEEE\/ACM Trans. on Networking"},{"key":"47_CR8","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. on Communications\u00a039, 426\u2013433 (1991)","journal-title":"IEEE Trans. on Communications"},{"key":"47_CR9","unstructured":"Chelbus, B.S., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in unknown radio networks. In: 11th ACM-SIAM SODA, pp. 861\u2013870"},{"key":"47_CR10","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":"B.S. Chelbus","year":"2000","unstructured":"Chelbus, B.S., Gasieniec, L., Gibbons, A., Ostlin, A., Robson, J.M.: Deterministic radio broadcasting. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 717\u2013728. Springer, Heidelberg (2000)"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Gasieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. In: Proc. 41st Symposium an Foundations of Computer Science (FOCS 2000), pp. 575\u2013581 (2000)","DOI":"10.1109\/SFCS.2000.892325"},{"key":"47_CR12","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 Symposium on Discrete Algorithms (SODA 2001), pp. 709\u2013718 (2001)","DOI":"10.1145\/383962.384040"},{"issue":"3","key":"47_CR13","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1109\/TIT.1982.1056510","volume":"IT-28","author":"R. Cruz","year":"1982","unstructured":"Cruz, R., Hajek, B.: A new upper bound to the throughput of a multi-access broadcast channel. IEEE Trans. Inf. Theory\u00a0IT-28(3), 402\u2013405 (1982)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"47_CR14","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0020-0190(00)00178-2","volume":"79","author":"G. Marco De","year":"2001","unstructured":"De Marco, G., Pelc, A.: Faster broadcasting in unknown radio networks. Information Processing Letter\u00a079, 53\u201356 (2001)","journal-title":"Information Processing Letter"},{"key":"47_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF02772959","volume":"51","author":"P. Erd\u00f6s","year":"1985","unstructured":"Erd\u00f6s, P., Frankl, P., Furedi, Z.: Families of finite sets in which no set is covered by the union of r others. Israel Journal of Math.\u00a051, 79\u201389 (1985)","journal-title":"Israel Journal of Math."},{"key":"47_CR16","unstructured":"Gabour, I., Mansour, Y.: Broadcast in radio networks. In: Proc. 6th Ann. ACMSIAM Symp. on Discrete Algorithms (SODA 1996), pp. 577\u2013585 (1996)"},{"key":"47_CR17","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 in radio networks. Discrete Applied Mathematics\u00a060, 219\u2013222 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"47_CR18","unstructured":"Indyk, P.: Explicit constructions of selector and related combinatorial structures, with applications. In: Proc. 13th Ann. ACM-SIAM Symposium on Disceret Algorithms (SODA 2002), pp. 697\u2013704 (2002)"},{"key":"47_CR19","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TIT.1964.1053689","volume":"10","author":"W.H. Kauz","year":"1964","unstructured":"Kauz, W.H., Singleton, R.R.C.: Nonrandom binary superimposed codes. IEEE Trans. on Information Theory\u00a010, 363\u2013377 (1964)","journal-title":"IEEE Trans. on Information Theory"},{"key":"47_CR20","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(Dlog(N\/D)) lower bound for broadcast in radio networks. SIAM J. on Computing\u00a027, 702\u2013712 (1998)","journal-title":"SIAM J. on Computing"},{"key":"47_CR21","unstructured":"M.: MOLLE, Unifications and extensions of the multiple access communications problem. Ph.D. Thesis, University of California, Los Angeles, Los Angeles, Calif. (July 1981)"},{"key":"47_CR22","doi-asserted-by":"crossref","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag product, and new constant degree expanders and extractors. In: Proc. 41st Symposium on Foundations of Computer Science (FOCS 2000), pp. 3\u201313 (2000)","DOI":"10.1109\/SFCS.2000.892006"},{"key":"47_CR23","doi-asserted-by":"crossref","unstructured":"Kowalski, D.R., Pelc, A.: Deterministic Broadcasting Time in Radio Networks of Unknown Topology. Accepted to Proc. 43rd Symposium on Foundations of Computer Science (FOCS 2002) (2002)","DOI":"10.1109\/SFCS.2002.1181883"},{"key":"47_CR24","unstructured":"Li, M., Vitanyi, P.: Introduction to Kolmogorov Complexity and it\u2019s applications, 2nd edn. Springer, Heidelberg"},{"key":"47_CR25","doi-asserted-by":"crossref","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley Series in Telecommunications (1990)","DOI":"10.1002\/0471200611"},{"key":"47_CR26","unstructured":"Errata regarding \u201dOn the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization\u201d (December 2002), available from http:\/\/www.wisdom.weizmann.ac.il\/oded\/pbgi.html"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T06:42:17Z","timestamp":1685774537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}