{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:48Z","timestamp":1770994128191,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1536026"],"award-info":[{"award-number":["CCF-1536026"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009226","name":"National Security Agency","doi-asserted-by":"publisher","award":["H98230-13-1-0228"],"award-info":[{"award-number":["H98230-13-1-0228"]}],"id":[{"id":"10.13039\/100009226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s00453-017-0336-y","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T05:25:30Z","timestamp":1497936330000},"page":"1013-1040","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Faster Information Gathering in Ad-Hoc Radio Tree Networks"],"prefix":"10.1007","volume":"80","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin P.","family":"Costello","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,20]]},"reference":[{"issue":"2","key":"336_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. Comput. Syst. Sci. 43(2), 290\u2013298 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"336_CR2","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00453-013-9816-x","volume":"67","author":"AF Anta","year":"2013","unstructured":"Anta, A.F., Mosteiro, M.A., Muoz, J.R.: Unbounded contention resolution in multiple-access channels. Algorithmica 67(3), 295\u2013314 (2013)","journal-title":"Algorithmica"},{"issue":"3","key":"336_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s004460050030","volume":"10","author":"D Bruschi","year":"1997","unstructured":"Bruschi, D., Del Pinto, M.: Lower bounds for the broadcast problem in mobile radio networks. Distrib. Comput. 10(3), 129\u2013135 (1997)","journal-title":"Distrib. Comput."},{"key":"336_CR4","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Kowalski, D.R., Pelc, A., Rokicki, M.A.: Efficient distributed communication in ad-hoc radio networks. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP\u201911), pp. 613\u2013624. (2011)","DOI":"10.1007\/978-3-642-22012-8_49"},{"issue":"1","key":"336_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s446-002-8028-1","volume":"15","author":"BS Chlebus","year":"2002","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)","journal-title":"Distrib. Comput."},{"key":"336_CR6","doi-asserted-by":"crossref","unstructured":"Christersson, M., Gasieniec, L., Lingas, A.: Gossiping with bounded size messages in ad hoc radio networks. In: Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP), pp. 377\u2013389. (2002)","DOI":"10.1007\/3-540-45465-9_33"},{"key":"336_CR7","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Costello, K., Gasieniec, L., Kowalski, D.R.: Information gathering in ad-hoc radio networks with tree topology. In: Proceedings of the 8th International Conference on Combinatorial Optimization and Applications (COCOA), pp. 129\u2013145. (2014)","DOI":"10.1007\/978-3-319-12691-3_11"},{"issue":"2","key":"336_CR8","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., Gasieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. J. Algorithms 43(2), 177\u2013189 (2002)","journal-title":"J. Algorithms"},{"issue":"2","key":"336_CR9","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1002\/net.10109","volume":"43","author":"M Chrobak","year":"2004","unstructured":"Chrobak, M., Gasieniec, L., Rytter, W.: A randomized algorithm for gossiping in radio networks. Networks 43(2), 119\u2013124 (2004)","journal-title":"Networks"},{"key":"336_CR10","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Manne, F., Xin, Q.: Faster centralized communication in radio networks. In: Proceedings of 17th International Symposium on Algorithms and Computation (ISAAC\u201906), pp. 339\u2013348. Springer, Berlin (2006)","DOI":"10.1007\/11940128_35"},{"key":"336_CR11","doi-asserted-by":"crossref","unstructured":"Clementi, A.E.F., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 709\u2013718. (2001)","DOI":"10.1145\/383962.384040"},{"issue":"1\u20133","key":"336_CR12","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00851-4","volume":"302","author":"AEF Clementi","year":"2003","unstructured":"Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theor. Comput. Sci. 302(1\u20133), 337\u2013364 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"336_CR13","unstructured":"Czumaj, A., Davies, P.: Almost optimal deterministic broadcast in radio networks. In: Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), (2016). To appear"},{"issue":"2","key":"336_CR14","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(2), 115\u2013143 (2006)","journal-title":"J. Algorithms"},{"key":"336_CR15","unstructured":"De Marco, G.: Distributed broadcast in unknown radio networks. In: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 208\u2013217. (2008)"},{"key":"336_CR16","doi-asserted-by":"crossref","unstructured":"De Marco, G., Kowalski, D.R.: Contention resolution in a non-synchronized multiple access channel. In: Proceedings of the 27th International Symposium on Parallel Distributed Processing (IPDPS), pp. 525\u2013533. (2013)","DOI":"10.1109\/IPDPS.2013.68"},{"issue":"3","key":"336_CR17","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1137\/140982763","volume":"44","author":"G De Marco","year":"2015","unstructured":"De Marco, G., Kowalski, D.R.: Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel. SIAM J. Comput. 44(3), 868\u2013888 (2015)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"336_CR18","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., F\u00fcredi, Z.: Families of finite sets in which no set is covered by the union of $$r$$ others. Israel J. Math. 51(1\u20132), 79\u201389 (1985)","journal-title":"Israel J. Math."},{"key":"336_CR19","doi-asserted-by":"crossref","unstructured":"Gasieniec, L.: On efficient gossiping in radio networks. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 2\u201314. (2009)","DOI":"10.1007\/978-3-642-11476-2_2"},{"key":"336_CR20","doi-asserted-by":"crossref","unstructured":"Gasieniec, L., Radzik, T., Xin, Q.: Faster deterministic gossiping in directed ad hoc radio networks. In: Proceedings of the 9th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 397\u2013407. (2004)","DOI":"10.1007\/978-3-540-27810-8_34"},{"key":"336_CR21","doi-asserted-by":"crossref","unstructured":"Kowalski, D.R.: On selection problem in radio networks. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 158\u2013166. (2005)","DOI":"10.1145\/1073814.1073843"},{"issue":"2","key":"336_CR22","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/S089548010342464X","volume":"18","author":"DR Kowalski","year":"2004","unstructured":"Kowalski, D.R., Pelc, A.: Faster deterministic broadcasting in ad hoc radio networks. SIAM J. Discrete Math. 18(2), 332\u2013346 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"336_CR23","doi-asserted-by":"crossref","unstructured":"Kowalski, D.R., Pelc, A.: Leader election in ad hoc radio networks: a keen ear helps. In: Proceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming (ICALP\u201909), pp. 521\u2013533. (2009)","DOI":"10.1007\/978-3-642-02930-1_43"},{"issue":"3","key":"336_CR24","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1137\/S0097539794279109","volume":"27","author":"E Kushilevitz","year":"1998","unstructured":"Kushilevitz, E., Mansour, Y.: An $$\\Omega (D\\log (N\/D))$$ lower bound for broadcast in radio networks. SIAM J. Comput. 27(3), 702\u2013712 (1998)","journal-title":"SIAM J. Comput."},{"key":"336_CR25","doi-asserted-by":"crossref","unstructured":"Liu, D., Prabhakaran, M.: On randomized broadcasting and gossiping in radio networks. In: Proceedings of the 8th International Computing and Combinatorics Conference (COCOON), pp. 340\u2013349. (2002)","DOI":"10.1007\/3-540-45655-4_37"},{"key":"336_CR26","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1130\/0016-7606(1952)63[1117:HAAOET]2.0.CO;2","volume":"63","author":"AN Strahler","year":"1952","unstructured":"Strahler, A.N.: Hypsometric (area-altitude) analysis of erosional topology. Geol. Soc. Am. Bull. 63, 1117\u20131142 (1952)","journal-title":"Geol. Soc. Am. Bull."},{"key":"336_CR27","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0012-365X(01)00265-5","volume":"246","author":"XG Viennot","year":"2003","unstructured":"Viennot, X.G.: A Strahler bijection between Dyck paths and planar trees. Discrete Math. 246, 317\u2013329 (2003)","journal-title":"Discrete Math."},{"issue":"1","key":"336_CR28","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-002-1010-5","volume":"36","author":"Xu Ying","year":"2003","unstructured":"Ying, Xu: An $$O(n^{1.5})$$ deterministic gossiping algorithm for radio networks. Algorithmica 36(1), 93\u201396 (2003)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0336-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0336-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0336-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:27:40Z","timestamp":1589696860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0336-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,20]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["336"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0336-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,20]]},"assertion":[{"value":"28 June 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}