{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:46:39Z","timestamp":1764557199006,"version":"3.37.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,9,4]],"date-time":"2009-09-04T00:00:00Z","timestamp":1252022400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s00453-009-9361-9","type":"journal-article","created":{"date-parts":[[2009,9,3]],"date-time":"2009-09-03T14:07:33Z","timestamp":1251986853000},"page":"719-734","source":"Crossref","is-referenced-by-count":20,"title":["Trade-offs Between the Size of Advice and Broadcasting Time in Trees"],"prefix":"10.1007","volume":"60","author":[{"given":"Emanuele G.","family":"Fusco","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,9,4]]},"reference":[{"key":"9361_CR1","unstructured":"Abiteboul, S., Kaplan, H., Milo, T.: Compact labeling schemes for ancestor queries. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp.\u00a0547\u2013556"},{"key":"9361_CR2","doi-asserted-by":"crossref","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. Comput. Syst. Sci. 43, 290\u2013298 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9361_CR3","doi-asserted-by":"crossref","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, 238\u2013256 (1990)","journal-title":"J. ACM"},{"key":"9361_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.2001.3081","volume":"176","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. Inf. Comput. 176, 1\u201321 (2002)","journal-title":"Inf. Comput."},{"key":"9361_CR5","unstructured":"Chierichetti, F.: Personal communication (2009)"},{"key":"9361_CR6","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.\u00a0709\u2013718","DOI":"10.1145\/383962.384040"},{"key":"9361_CR7","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: Proc. 32th International Colloquium on Automata, Languages and Programming (ICALP 2005). LNCS, vol.\u00a03580, pp.\u00a0335\u2013346","DOI":"10.1007\/11523468_28"},{"key":"9361_CR8","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. In: Proc. 44th Symp. on Foundations of Computer Science (FOCS 2003), pp.\u00a0492\u2013501","DOI":"10.1109\/SFCS.2003.1238222"},{"key":"9361_CR9","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/j.tcs.2004.07.031","volume":"326","author":"A. Dessmark","year":"2004","unstructured":"Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. Theor. Comput. Sci. 326, 343\u2013362 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9361_CR10","doi-asserted-by":"crossref","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, 187\u2013201 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"9361_CR11","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 287, 449\u2013471 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9361_CR12","doi-asserted-by":"crossref","unstructured":"Elkin, M., Kortsarz, G.: A sublogarithmic approximation algorithm for the undirected telephone broadcast problem: a path out of a jungle. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp.\u00a076\u201385","DOI":"10.1145\/509907.509972"},{"key":"9361_CR13","doi-asserted-by":"crossref","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 Comput. 16, 121\u2013163 (2003)","journal-title":"Distributed Comput."},{"key":"9361_CR14","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed computing with advice: information sensitivity of graph coloring. In: Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007). LNCS, vol.\u00a04596, pp.\u00a0231\u2013242","DOI":"10.1007\/978-3-540-73420-8_22"},{"key":"9361_CR15","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication problems. In: Proc. 25th Ann. ACM Symposium on Principles of Distributed Computing (PODC 2006), pp.\u00a0179\u2013187","DOI":"10.1145\/1146381.1146410"},{"key":"9361_CR16","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). LNCS, vol.\u00a04162, pp.\u00a024\u201337","DOI":"10.1007\/11821069_2"},{"key":"9361_CR17","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: Proc. 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), pp.\u00a0154\u2013160","DOI":"10.1145\/1248377.1248402"},{"key":"9361_CR18","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp.\u00a0210\u2013219"},{"key":"9361_CR19","doi-asserted-by":"crossref","unstructured":"Ilcinkas, D., Kowalski, D., Pelc, A.: Fast radio broadcasting with advice. In: Proc. 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008). LNCS, vol.\u00a05058, pp.\u00a0291\u2013305","DOI":"10.1007\/978-3-540-69355-0_24"},{"key":"9361_CR20","unstructured":"Katz, M., Katz, N., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp.\u00a0927\u2013936"},{"key":"9361_CR21","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC 2005), pp.\u00a09\u201318","DOI":"10.1145\/1073814.1073817"},{"key":"9361_CR22","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/S0895480193245923","volume":"8","author":"G. Kortsarz","year":"1995","unstructured":"Kortsarz, G., Peleg, D.: Approximation algorithms for minimum time broadcast. SIAM J. Discrete Math. 8, 401\u2013427 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"9361_CR23","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00446-005-0126-7","volume":"18","author":"D. Kowalski","year":"2005","unstructured":"Kowalski, D., Pelc, A.: Broadcasting in undirected ad hoc radio networks. Distrib. Comput. 18, 43\u201357 (2005)","journal-title":"Distrib. Comput."},{"key":"9361_CR24","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s00446-006-0007-8","volume":"19","author":"D. Kowalski","year":"2007","unstructured":"Kowalski, D., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19, 185\u2013195 (2007)","journal-title":"Distrib. Comput."},{"key":"9361_CR25","doi-asserted-by":"crossref","unstructured":"Lynch, N.: A hundred impossibility proofs for distributed computing. In: Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (PODC 1989), pp.\u00a01\u201328","DOI":"10.1145\/72981.72982"},{"key":"9361_CR26","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s00446-007-0021-5","volume":"19","author":"A. Pelc","year":"2007","unstructured":"Pelc, A.: Activating anonymous ad hoc radio networks. Distrib. Comput. 19, 361\u2013371 (2007)","journal-title":"Distrib. Comput."},{"issue":"5","key":"9361_CR27","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/TC.1981.1675796","volume":"C-30","author":"A. Proskurowski","year":"1981","unstructured":"Proskurowski, A.: Minimum broadcast trees. IEEE Trans. Comput. C-30(5), 363\u2013366 (1981)","journal-title":"IEEE Trans. Comput."},{"key":"9361_CR28","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1137\/0210052","volume":"10","author":"P.J. Slater","year":"1981","unstructured":"Slater, P.J., Cockayne, E.J., Hedetniemi, S.T.: Information dissemination in trees. SIAM J. Comput. 10, 692\u2013701 (1981)","journal-title":"SIAM J. Comput."},{"key":"9361_CR29","doi-asserted-by":"crossref","unstructured":"Soguet, D., Nisse, N.: Graph searching with advice. In: Proc. 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2007). LNCS, vol.\u00a04474, pp.\u00a051\u201365","DOI":"10.1007\/978-3-540-72951-8_6"},{"issue":"1","key":"9361_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9361-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9361-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9361-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T23:46:00Z","timestamp":1739317560000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9361-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,4]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["9361"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9361-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,9,4]]}}}