{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T10:12:33Z","timestamp":1760523153122},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T00:00:00Z","timestamp":1402358400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00453-014-9905-5","type":"journal-article","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T14:28:17Z","timestamp":1402410497000},"page":"87-114","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Initializing Sensor Networks of Non-uniform Density in the Weak Sensor Model"],"prefix":"10.1007","volume":"73","author":[{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel A.","family":"Mosteiro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,6,10]]},"reference":[{"issue":"4","key":"9905_CR1","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/S1389-1286(01)00302-4","volume":"38","author":"IF Akyildiz","year":"2002","unstructured":"Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cyirci, E.: Wireless sensor networks: a survey. Comput. Netw. 38(4), 393\u2013422 (2002)","journal-title":"Comput. Netw."},{"key":"9905_CR2","doi-asserted-by":"crossref","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 multi-hop radio networks: an exponential gap between determinism and randomization. J. Comput. Sys. Sci. 45, 104\u2013126 (1992)","journal-title":"J. Comput. Sys. Sci."},{"key":"9905_CR3","doi-asserted-by":"crossref","unstructured":"Blough, D.M., Leoncini, M., Resta, G., Santi, P.: The k-neigh protocol for symmetric topology control in ad hoc networks. In: Proceedings of the 4th ACM international symposium on mobile ad hoc networking and computing, pp. 141\u2013152 (2003).","DOI":"10.1145\/778415.778433"},{"key":"9905_CR4","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/978-1-4615-0013-1_11","volume-title":"Handbook on Randomized Computing","author":"B Chlebus","year":"2001","unstructured":"Chlebus, B.: Randomized communication in radio networks. In: Pardalos, P., Rajasekaran, S., Reif, J., Rolim, J. (eds.) Handbook on Randomized Computing, vol. 1, pp. 401\u2013456. Kluwer Academic Publishers, Norwell (2001)"},{"key":"9905_CR5","doi-asserted-by":"crossref","unstructured":"Chlebus, B., Ga\u0327sieniec, L., Lingas, A., Pagourtzis, A.: Oblivious gossiping in ad-hoc radio networks. In: Proceedings of 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 44\u201351 (2001).","DOI":"10.1145\/381448.381454"},{"key":"9905_CR6","unstructured":"Dolev, S., Segal, M., Shpungin, H.: Bounded-hop strong connectivity for flocking swarms. In: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th International Symposium on, pp. 177\u2013185 (2010)."},{"issue":"3","key":"9905_CR7","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1109\/TMC.2012.27","volume":"12","author":"S Dolev","year":"2013","unstructured":"Dolev, S., Segal, M., Shpungin, H.: Bounded-hop energy-efficient liveness of flocking swarms. IEEE Trans. Mobile Comput. 12(3), 516\u2013528 (2013). doi: 10.1109\/TMC.2012.27","journal-title":"IEEE Trans. Mobile Comput."},{"key":"9905_CR8","doi-asserted-by":"crossref","unstructured":"Farach-Colton, M., Fernandes, R.J., Mosteiro, M.A.: Lower bounds for clear transmissions in radio networks. In: Proceedings of the 7th Latin American Theoretical Informatics Symposium Lecture Notes in Computer Science, vol. 3887, pp. 447\u2013454. Springer-Verlag, Berlin (2006).","DOI":"10.1007\/11682462_42"},{"issue":"4","key":"9905_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1597036.1597040","volume":"5","author":"M Farach-Colton","year":"2009","unstructured":"Farach-Colton, M., Fernandes, R.J., Mosteiro, M.A.: Bootstrapping a hop-optimal network in the weak sensor model. ACM Trans. Algo. 5(4), 1\u201330 (2009)","journal-title":"ACM Trans. Algo."},{"key":"9905_CR10","doi-asserted-by":"crossref","unstructured":"Farach-Colton, M., Mosteiro, M.A.: Initializing sensor networks of non-uniform density in the weak sensor model. In: Proceedings of 10th International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 4619, pp. 565\u2013576. Springer-Verlag, Berlin (2007).","DOI":"10.1007\/978-3-540-73951-7_49"},{"key":"9905_CR11","doi-asserted-by":"crossref","unstructured":"Fern\u00e1ndez Anta, A., Mosteiro, M.A.: Contention resolution in multiple-access channels: $$k$$ k -selection in radio networks. In: Proceedings of the 16th Annual Conference on Computing and Combinatorics, Lecture Notes in Computer Science, vol. 6196, pp. 378\u2013388. Springer (2010).","DOI":"10.1142\/S1793830910000796"},{"issue":"1","key":"9905_CR12","first-page":"95","volume":"13","author":"A Fern\u00e1ndez Anta","year":"2011","unstructured":"Fern\u00e1ndez Anta, A., Mosteiro, M.A., Thraves, C.: Deterministic recurrent communication and synchronization in restricted sensor networks. Discret. Math. Theoret. Comput. Sci. 13(1), 95\u2013112 (2011)","journal-title":"Discret. Math. Theoret. Comput. Sci."},{"key":"9905_CR13","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2011.10.018","volume":"418","author":"A Fern\u00e1ndez Anta","year":"2012","unstructured":"Fern\u00e1ndez Anta, A., Mosteiro, M.A., Thraves, C.: Deterministic recurrent communication in restricted sensor networks. Theoret. Comput. Sci. 418, 37\u201347 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"9905_CR14","doi-asserted-by":"crossref","unstructured":"Ger\u00e8b-Graus, M., Tsantilas, T.: Efficient optical communication in parallel computers. In: Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 41\u201348 (1992)","DOI":"10.1145\/140901.140906"},{"key":"9905_CR15","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Mitra, P.: Distributed connectivity of wireless networks. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC \u201912, pp. 205\u2013214. ACM, New York (2012). doi: 10.1145\/2332432.2332469","DOI":"10.1145\/2332432.2332469"},{"issue":"3","key":"9905_CR16","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s00224-005-1144-3","volume":"38","author":"T Jurdzi\u0144ski","year":"2005","unstructured":"Jurdzi\u0144ski, T., Stachowiak, G.: Probabilistic algorithms for the wakeup problem in single-hop radio networks. Theory Comput. Sys. 38(3), 347\u2013367 (2005)","journal-title":"Theory Comput. Sys."},{"key":"9905_CR17","unstructured":"Karl, H., Willig, A.: A short survey of wireless networks. Tech. Rep. TKN-03-018. Technical University Berlin (2003)"},{"key":"9905_CR18","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/j.tcs.2004.04.017","volume":"333","author":"DR Kowalski","year":"2005","unstructured":"Kowalski, D.R., Pelc, A.: Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism. Theoret. Comput. Sci. 333, 355\u2013371 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"9905_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Initializing newly deployed ad hoc and sensor networks. In: Proceedings of the 10th ACM Annual International Conference on Mobile Computing and Networking (2004).","DOI":"10.1145\/1023720.1023746"},{"key":"9905_CR20","unstructured":"Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: End-to-end packet-scheduling in wireless ad-hoc networks. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1021\u20131030 (2004)"},{"issue":"3","key":"9905_CR21","doi-asserted-by":"crossref","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}))$$ \u03a9 ( D log ( N \/ D ) ) lower bound for broadcast in radio networks. SIAM J. Comput. 27(3), 702\u2013712 (1998)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"9905_CR22","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/1364782.1364804","volume":"51","author":"P Levis","year":"2008","unstructured":"Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., Patel, N., Polastre, J., Shenker, S., Szewczyk, R., Woo, A.: The emergence of a networking primitive in wireless sensor networks. Commun. ACM 51(7), 99\u2013106 (2008)","journal-title":"Commun. ACM"},{"key":"9905_CR23","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(94)90133-3","volume":"52","author":"CU Martel","year":"1994","unstructured":"Martel, C.U.: Maximum finding on a multiple access broadcast network. Inf. Process. Lett. 52, 7\u201313 (1994)","journal-title":"Inf. Process. Lett."},{"key":"9905_CR24","unstructured":"Mitrinovi\u0107, D.S.: Elementary Inequalities. P. Noordhoff Ltd., Groningen (1964)"},{"key":"9905_CR25","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9905_CR26","unstructured":"Muthukrishnan, S., Pandurangan, G.: The bin-covering technique for thresholding random geometric graph properties. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 989\u2013998 (2005)"},{"key":"9905_CR27","doi-asserted-by":"crossref","unstructured":"Nakano, K., Olariu, S.: Energy-efficient initialization protocols for radio networks with no collision detection. In: Proceedings of the International Conference Parallel Processing, pp. 263\u2013270 (2000)","DOI":"10.1109\/ICPP.2000.876141"},{"key":"9905_CR28","unstructured":"Ponduru, V.A.S., Bharathidasan, A.: Sensor networks: An overview. Tech. rep., University of California, Davis (2003). http:\/\/wwwcsif.cs.ucdavis.edu\/bharathi\/sensor\/survey.pdf . Accessed 17 Mar 2013"},{"key":"9905_CR29","unstructured":"Rentala, P., Musumuri, R., Saxena, U., Gandham, S.: Survey on sensor networks. http:\/\/citeseer.nj.nec.com\/479874.html . Accessed 17 Mar 2013"},{"issue":"2","key":"9905_CR30","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/1024916.1024920","volume":"5","author":"LG Roberts","year":"1975","unstructured":"Roberts, L.G.: Aloha packet system with and without slots and capture. Comput. Commun. Rev. 5(2), 28\u201342 (1975)","journal-title":"Comput. Commun. Rev."},{"issue":"5","key":"9905_CR31","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/98.878532","volume":"7","author":"K Sohrabi","year":"2000","unstructured":"Sohrabi, K., Gao, J., Ailawadhi, V., Pottie, G.J.: Protocols for self-organization of a wireless sensor network. Pers. Commun. IEEE 7(5), 16\u201327 (2000)","journal-title":"Pers. Commun. IEEE"},{"key":"9905_CR32","doi-asserted-by":"crossref","unstructured":"Song, W., Wang, Y., Li, X., Frieder, O.: Localized algorithms for energy efficient topology in wireless ad hoc networks. In: Proceedings of the 5th ACM International Symposium on Mobile Ad hoc Networking and Computing, pp. 98\u2013108 (2004)","DOI":"10.1145\/989459.989473"},{"issue":"32","key":"9905_CR33","first-page":"32:1","volume":"43","author":"B Wang","year":"2011","unstructured":"Wang, B.: Coverage problems in sensor networks: a survey. ACM Comput. Surv. 43(32), 32:1\u201332:53 (2011)","journal-title":"ACM Comput. Surv."},{"key":"9905_CR34","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1137\/0215032","volume":"15","author":"DE Willard","year":"1986","unstructured":"Willard, D.E.: Log-logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput. 15, 468\u2013477 (1986)","journal-title":"SIAM J. Comput."},{"key":"9905_CR35","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1109\/MNET.2006.1637928","volume":"20","author":"O Younis","year":"2006","unstructured":"Younis, O., Krunz, M., Ramasubramanian, S.: Node clustering in wireless sensor networks: recent developments and deployment challenges. IEEE Netw. Mag. 20, 20\u201325 (2006)","journal-title":"IEEE Netw. Mag."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9905-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9905-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9905-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:14Z","timestamp":1559123114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9905-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,10]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9905"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9905-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,10]]}}}