{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:14:08Z","timestamp":1743092048200,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"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_14","type":"book-chapter","created":{"date-parts":[[2009,11,17]],"date-time":"2009-11-17T11:17:06Z","timestamp":1258456626000},"page":"357-377","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Data Gathering in Wireless Networks"],"prefix":"10.1007","author":[{"given":"Vincenzo","family":"Bonifaci","sequence":"first","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Korteweg","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,9]]},"reference":[{"issue":"4","key":"14_CR1","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/S1389-1286(01)00302-4","volume":"38","author":"I. F. Akyildiz","year":"2002","unstructured":"Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Computer Networks 38(4), 393\u2013422 (2002)","journal-title":"Computer Networks"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"issue":"1","key":"14_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 multi-hop radio networks: an exponential gap between determinism and randomization. Journal of Computer and System Sciences 45(1), 104\u2013126 (1992)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"14_CR4","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 Journal on Computing 22(4), 875\u2013887 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Bermond, J. C., Corr\u00eaa, R. C., Yu, M. L.: Gathering algorithms on paths under interference constraints. In: Proceedings of the 6th Italian Conference Algorithms and Complexity, Lecture Notes in Computer Science, vol. 3998, pp. 115\u2013126. Springer (2006). Full version to appear in Discrete Mathematics","DOI":"10.1007\/11758471_14"},{"key":"14_CR6","first-page":"85","volume-title":"Gathering in specific radio networks. In:","author":"J. C. Bermond","year":"2006","unstructured":"Bermond, J. C., Galtier, J., Klasing, R., Morales, N., P\u00e9rennes, S.: Gathering in specific radio networks. In: 8\u00e8mes Rencontres Francophones sur les Aspects Algorithmiques des T\u00e9l\u00e9communications, pp. 85\u201388. Tr\u00e9gastel, France (2006)"},{"issue":"2","key":"14_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1142\/S0129626406002551","volume":"16","author":"J. C. Bermond","year":"2006","unstructured":"Bermond, J. C., Galtier, J., Klasing, R., Morales, N., P\u00e9rennes, S.: Hardness and approximation of gathering in static radio networks. Parallel Processing Letters 16(2), 165\u2013183 (2006)","journal-title":"Parallel Processing Letters"},{"key":"14_CR8","first-page":"75","volume-title":"Hardness and approximation of gathering in static radio networks.","author":"J. C. Bermond","year":"2006","unstructured":"Bermond, J. C., Galtier, J., Klasing, R., Morales, N., P\u00e9rennes, S.: Hardness and approximation of gathering in static radio networks. In: Proc. Foundation and Algorithms for Wireless Networking, pp. 75\u201379. Pisa, Italy (2006)"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Bermond, J. C., Gargano, L., Rescigno, A.: Gathering with minimum delay in tree sensor networks. In: Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity, Lecture Notes in Computer Science, vol. 5058, pp. 262\u2013276. Springer (2008)","DOI":"10.1007\/978-3-540-69355-0_22"},{"key":"14_CR10","first-page":"103","volume-title":"Efficient gathering in radio grids with interference.","author":"J. C. Bermond","year":"2005","unstructured":"Bermond, J. C., Peters, J.: Efficient gathering in radio grids with interference. In: Septi\u00e9mes Rencontres Francophones sur les Aspects Algorithmiques des T\u00e9l\u00e9communications, pp. 103\u2013106. Presqu\u2019\u00eele de Giens, France (2005)"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Bermond, J. C., Yu, M. L.: Optimal gathering algorithms in multi-hop radio tree networks with interferences. In: Proc. of the Int. Conf. on Ad-Hoc, Mobile, and Wireless Networks, pp. 204\u2013217 (2008)","DOI":"10.1007\/978-3-540-85209-4_16"},{"key":"14_CR12","first-page":"16","volume":"22","author":"P. Bertin","year":"2005","unstructured":"Bertin, P., Bresse, J. F., Sage, B.: Acc\u00e8s haut d\u00e9bit en zone rurale: une solution \u201cad hoc\u201d. France Telecom R & D 22, 16\u201318 (2005)","journal-title":"France Telecom R & D"},{"issue":"5","key":"14_CR13","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.orl.2008.06.001","volume":"36","author":"V. Bonifaci","year":"2008","unstructured":"Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L.: An approximation algorithm for the wireless gathering problem. Operations Research Letters 36(5), 605\u2013608 (2008)","journal-title":"Operations Research Letters"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L.: The distributed wireless gathering problem. In: Proc. Int. Conf. on Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, vol. 5034, pp. 72\u201383. Springer (2008)","DOI":"10.1007\/978-3-540-68880-8_9"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L.: Minimizing average flow time in sensor data gathering. In: Proc. 4th Workshop on Algorithmic Aspects of Wireless Sensor Networks, Lecture Notes in Computer Science, vol. 5389, pp. 18\u201329. Springer (2008)","DOI":"10.1007\/978-3-540-92862-1_3"},{"key":"14_CR16","unstructured":"Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L.: Minimizing flow time in the wireless gathering problem. In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, pp. 109\u2013120 (2008)"},{"key":"14_CR17","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998)"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Boukerche, A. (ed.): Handbook of Algorithms for Wireless Networking and Mobile Computing. Chapman & Hall (2005)","DOI":"10.1201\/9781420035094"},{"issue":"1","key":"14_CR19","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1137\/S0097539791217695","volume":"24","author":"I. Cidon","year":"1995","unstructured":"Cidon, I., Kutten, S., Mansour, Y., Peleg, D.: Greedy packet scheduling. SIAM Journal on Computing 24(1), 148\u2013157 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR20","volume-title":"PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks.","author":"S. Coleri","year":"2002","unstructured":"Coleri, S.: PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks. Master\u2019s thesis, University of California, Berkeley (2002)"},{"issue":"1","key":"14_CR21","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jda.2004.05.001","volume":"3","author":"W. Duckworth","year":"2005","unstructured":"Duckworth, W., Manlove, D., Zito, M.: On the approximability of the maximum induced matching problem. Journal of Discrete Algorithms 3(1), 79\u201391 (2005)","journal-title":"Journal of Discrete Algorithms"},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1109\/JSAC.2004.830927","volume":"22","author":"C. Florens","year":"2004","unstructured":"Florens, C., Franceschetti, M., McEliece, R. J.: Lower bounds on data collection time in sensory networks. IEEE Journal on Selected Areas in Communications 22, 1110\u2013 1120 (2004)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"14_CR23","unstructured":"Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman (1979)"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"Gargano, L.: Time optimal gathering in sensor networks. In: Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity, Lecture Notes in Computer Science, vol. 4474, pp. 7\u201310. Springer (2007)","DOI":"10.1007\/978-3-540-72951-8_2"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Gargano, L., Rescigno, A. A.: Optimally fast data gathering in sensor networks. In: Proceedings of the 31st Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 4162, pp. 399\u2013411. Springer (2006)","DOI":"10.1007\/11821069_35"},{"key":"14_CR26","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems \u2014 Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer (2001)"},{"key":"14_CR27","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.tcs.2008.06.048","volume":"406","author":"R. Klasing","year":"2008","unstructured":"Klasing, R., Morales, N., P\u00e9rennes, S.: On the complexity of bandwidth allocation in radio networks. Theoretical Computer Science 406, 225\u2013239 (2008)","journal-title":"Theoretical Computer Science"},{"key":"14_CR28","unstructured":"Korteweg, P.: Online Gathering Algorithms for Wireless Networks. Ph.D. thesis, Eindhoven Technical University (2008)"},{"key":"14_CR29","unstructured":"Kumar, V. S. A., Marathe, M. V., Parthasarathy, S., Srinivasan, A.: End-to-end packet-scheduling in wireless ad-hoc networks. In: J. I. Munro (ed.) Proceedings of the 15th Symposium on Discrete Algorithms, pp. 1021\u20131030 (2004)"},{"key":"14_CR30","unstructured":"Morales, N.: Algorithmique de r\u00e9seaux de communication radio modelis\u00e9s par de graphes. PhD thesis, Universit\u00e9 de Nice-Sophia Antipolis (2007)"},{"key":"14_CR31","unstructured":"Papadimitriou, C. H.: Computational Complexity. Addison-Wesley (1994)"},{"key":"14_CR32","unstructured":"Perkins, C. E. (ed.): Ad Hoc Networking. Addison-Wesley Professional (2001)"},{"issue":"5","key":"14_CR33","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/332833.332838","volume":"43","author":"G. J. Pottie","year":"2000","unstructured":"Pottie, G. J., Kaiser, W. J.: Wireless integrated network sensors. Communications of the ACM 43(5), 51\u201358 (2000)","journal-title":"Communications of the ACM"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"Raghavendra, C. S., Sivalingam, K. M., Znati, T. (eds.): Wireless Sensor Networks. Springer (2004)","DOI":"10.1007\/b117506"},{"key":"14_CR35","doi-asserted-by":"crossref","unstructured":"Revah, Y., Segal, M.: Improved algorithms for data-gathering time in sensor networks II: Ring, tree and grid topologies. In: Proc. of the 3rd IEEE Int. Conf. on Networking and Services (2007)","DOI":"10.1109\/ICNS.2007.70"},{"key":"14_CR36","doi-asserted-by":"crossref","unstructured":"Revah, Y., Segal, M.: Improved lower bounds for data-gathering time in sensor networks. In: Proc. of the 3rd IEEE Int. Conf. on Networking and Services (2007)","DOI":"10.1109\/ICNS.2007.71"},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"Schmid, S., Wattenhofer, R.: Algorithmic models for sensor networks. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium (2006)","DOI":"10.1109\/IPDPS.2006.1639417"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"Segal, M., Yedidsion, L.: On real time data-gathering in sensor networks. In: Proc. of the 3rd IEEE Int. Conf. on Mobile, Adhoc and Sensor Systems (2007)","DOI":"10.1109\/MOBHOC.2007.4428754"},{"key":"14_CR39","volume-title":"Approximation Algorithms.","author":"V. V. Vazirani","year":"2001","unstructured":"Vazirani, V. V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"14_CR40","doi-asserted-by":"crossref","unstructured":"Yao, A. C. C.: Probabilistic computations: Towards a unified measure of complexity. In: Proc. of the 18th Symp. on the Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"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_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,18]],"date-time":"2023-02-18T01:16:20Z","timestamp":1676682980000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02250-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022494","9783642022500"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02250-0_14","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"}}]}}