{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T04:35:28Z","timestamp":1780806928882,"version":"3.54.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,9]],"date-time":"2014-10-09T00:00:00Z","timestamp":1412812800000},"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":[[2016,1]]},"DOI":"10.1007\/s00453-014-9939-8","type":"journal-article","created":{"date-parts":[[2014,10,8]],"date-time":"2014-10-08T18:15:49Z","timestamp":1412792149000},"page":"117-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Convergecast and Broadcast by Power-Aware Mobile Agents"],"prefix":"10.1007","volume":"74","author":[{"given":"Julian","family":"Anaya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e9r\u00e9mie","family":"Chalopin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jurek","family":"Czyzowicz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnaud","family":"Labourel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yann","family":"Vax\u00e8s","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,10,9]]},"reference":[{"issue":"5","key":"9939_CR1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1735223.1735245","volume":"53","author":"S Albers","year":"2010","unstructured":"Albers, S.: Energy-efficient algorithms. Commun. ACM 53(5), 86\u201396 (2010)","journal-title":"Commun. ACM"},{"key":"9939_CR2","doi-asserted-by":"crossref","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 416\u2013425 (1997)","DOI":"10.1145\/258533.258630"},{"key":"9939_CR3","volume-title":"The Theory of Search Games and Rendezvous","author":"S Alpern","year":"2003","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous, vol. 55. Springer, Berlin (2003)"},{"key":"9939_CR4","doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C.: An optimal bound for the mst algorithm to compute energy efficient broadcast trees in wireless networks. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, vol. 3580, pp. 1139\u20131150 (2005)","DOI":"10.1007\/11523468_92"},{"issue":"5","key":"9939_CR5","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1109\/70.795787","volume":"15","author":"H Ando","year":"1999","unstructured":"Ando, H., Oasa, Y., Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Autom. 15(5), 818\u2013828 (1999)","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"4","key":"9939_CR6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235\u2013253 (2006)","journal-title":"Distrib. Comput."},{"key":"9939_CR7","first-page":"1942","volume":"3","author":"V Annamalai","year":"2003","unstructured":"Annamalai, V., Gupta, S., Schwiebert, L.: On tree-based convergecasting in wireless sensor networks. IEEE Wirel. Commun. Netw. 3, 1942\u20131947 (2003)","journal-title":"IEEE Wirel. Commun. Netw."},{"key":"9939_CR8","doi-asserted-by":"crossref","unstructured":"Augustine, J., Irani, S., Swamy, C.: Optimal power-down strategies. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 530\u2013539 (2004)","DOI":"10.1109\/FOCS.2004.50"},{"issue":"1\u20132","key":"9939_CR9","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0166-218X(95)00054-U","volume":"68","author":"I Averbakh","year":"1996","unstructured":"Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Appl. Math. 68(1\u20132), 17\u201332 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9939_CR10","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1006\/inco.1999.2795","volume":"152","author":"B Awerbuch","year":"1999","unstructured":"Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Inf. Comput. 152(2), 155\u2013172 (1999)","journal-title":"Inf. Comput."},{"issue":"2","key":"9939_CR11","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B Awerbuch","year":"1990","unstructured":"Awerbuch, B., Goldreich, O., Vainish, R., Peleg, D.: A trade-off between information and communication in broadcast protocols. J. ACM 37(2), 238\u2013256 (1990)","journal-title":"J. ACM"},{"key":"9939_CR12","doi-asserted-by":"crossref","unstructured":"Azar, Y.: On-line load balancing. In: Fiat A., Woeginger G. (eds.) Online Algorithms Lecture notes in Computer Science, vol. 1442, pp. 178\u2013195 (1998)","DOI":"10.1007\/BFb0029569"},{"issue":"2","key":"9939_CR13","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R Baezayates","year":"1993","unstructured":"Baezayates, R., Culberson, J., Rawlins, G.: Searching in the plane. Inf. Comput. 106(2), 234\u2013252 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"9939_CR14","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. Syst. Sci. 45(1), 104\u2013126 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"9939_CR15","doi-asserted-by":"crossref","unstructured":"Bender, M., Slonim, D.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 75\u201385 (1994)","DOI":"10.1109\/SFCS.1994.365703"},{"issue":"1","key":"9939_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.2001.3081","volume":"176","author":"MA Bender","year":"2002","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: exploring and mapping directed graphs. Inf. Comput. 176(1), 1\u201321 (2002)","journal-title":"Inf. Comput."},{"issue":"2\u20133","key":"9939_CR17","first-page":"231","volume":"18","author":"M Betke","year":"1995","unstructured":"Betke, M., Rivest, R., Singh, M.: Piecemeal learning of an unknown environment. Mach. Learn. 18(2\u20133), 231\u2013254 (1995)","journal-title":"Mach. Learn."},{"issue":"1","key":"9939_CR18","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1137\/S0097539791194931","volume":"26","author":"A Blum","year":"1997","unstructured":"Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM J. Comput. 26(1), 110\u2013137 (1997)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9939_CR19","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/s10951-009-0123-y","volume":"12","author":"D Bunde","year":"2009","unstructured":"Bunde, D.: Power-aware scheduling for makespan and flow. J. Sched. 12(5), 489\u2013500 (2009)","journal-title":"J. Sched."},{"issue":"1","key":"9939_CR20","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/TMC.2011.26","volume":"11","author":"F Chen","year":"2012","unstructured":"Chen, F., Johnson, M., Alayev, Y., Bar-Noy, A., La Porta, T.: Who, when, where: timeslot assignment to mobile clients. IEEE Trans. Mob. Comput. 11(1), 73\u201385 (2012)","journal-title":"IEEE Trans. Mob. Comput."},{"key":"9939_CR21","doi-asserted-by":"crossref","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Proceedings of the International Colloquium of Automata. Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 2719 pp. 1181\u20131196. Springer, Berlin (2003)","DOI":"10.1007\/3-540-45061-0_90"},{"issue":"6","key":"9939_CR22","doi-asserted-by":"crossref","first-page":"1516","DOI":"10.1137\/S0097539704446475","volume":"34","author":"R Cohen","year":"2005","unstructured":"Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516\u20131528 (2005)","journal-title":"SIAM J. Comput."},{"key":"9939_CR23","doi-asserted-by":"crossref","unstructured":"Cord-Landwehr, A., Degener, B., Fischer, M., H\u00fcllmann, M., Kempkes, B., Klaas, A., Kling, P., Kurras, S., M\u00e4rtens, M., Meyer auf der Heide, F., Raupach, C., Swierkot, K., Warner, D., Weddemann, C., Wonisch, D.: A new approach for analyzing convergence algorithms for mobile robots. In: Aceto L., Henzinger M., Sgall J. (eds.) Proceedings of the International Colloquium of Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 6756 pp. 650\u2013661 (2011)","DOI":"10.1007\/978-3-642-22012-8_52"},{"key":"9939_CR24","doi-asserted-by":"crossref","unstructured":"Das, S., Flocchini, P., Santoro, N., Yamashita, M.: On the computational power of oblivious robots: forming a series of geometric patterns. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 267\u2013276 (2010)","DOI":"10.1145\/1835698.1835761"},{"issue":"3","key":"9939_CR25","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8","volume":"32","author":"X Deng","year":"1999","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265\u2013297 (1999)","journal-title":"J. Graph Theory"},{"key":"9939_CR26","doi-asserted-by":"crossref","unstructured":"Dynia, M., Korzeniowski, M., Schindelhauer, C.: Power-aware collective tree exploration. In: Architecture of Computing Systems (ARCS), Lecture Notes in Computer Science, vol. 3894, pp. 341\u2013351 (2006)","DOI":"10.1007\/11682127_24"},{"issue":"1\u20133","key":"9939_CR27","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.tcs.2005.01.001","volume":"337","author":"P Flocchini","year":"2005","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1\u20133), 147\u2013168 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9939_CR28","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166\u2013177 (2006)","journal-title":"Networks"},{"issue":"2","key":"9939_CR29","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/0207017","volume":"7","author":"G Frederickson","year":"1978","unstructured":"Frederickson, G., Hecht, M., Kim, C.: Approximation algorithms for some routing problems. SIAM J. Comput. 7(2), 178\u2013193 (1978)","journal-title":"SIAM J. Comput."},{"key":"9939_CR30","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"4","key":"9939_CR31","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/1290672.1290678","volume":"3","author":"S Irani","year":"2007","unstructured":"Irani, S., Shukla, S., Gupta, R.: Algorithms for power savings. ACM Trans. Algorithms 3(4), 41 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9939_CR32","doi-asserted-by":"crossref","unstructured":"Kesselman, A., Kowalski, D.R.: Fast distributed algorithm for convergecast in ad hoc geometric radio networks. J. Parallel Distrib. Comput. 66(4):578\u2013585, 2006. Algorithms for Wireless and Ad-Hoc Networks","DOI":"10.1016\/j.jpdc.2005.11.004"},{"key":"9939_CR33","doi-asserted-by":"crossref","unstructured":"Krishnamachari, B., Estrin, D., Wicker, S.: The impact of data aggregation in wireless sensor networks. In: Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops, pp. 575\u2013578 (2002)","DOI":"10.1109\/ICDCSW.2002.1030829"},{"key":"9939_CR34","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.tcs.2012.06.034","volume":"463","author":"N Megow","year":"2012","unstructured":"Megow, N., Mehlhorn, K., Schweitzer, P.: Online graph exploration: new results on old and new algorithms. Theor. Comput. Sci. 463, 62\u201372 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9939_CR35","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1109\/COMST.2006.283821","volume":"8","author":"R Rajagopalan","year":"2006","unstructured":"Rajagopalan, R., Varshney, P.: Data-aggregation techniques in sensor networks: a survey. IEEE Commun. Surv. Tutor. 8(4), 48\u201363 (2006)","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"9939_CR36","doi-asserted-by":"crossref","DOI":"10.1002\/0470072644","volume-title":"Design and Analysis of Distributed Algorithms","author":"N Santoro","year":"2006","unstructured":"Santoro, N.: Design and Analysis of Distributed Algorithms, vol. 56. Wiley, New York (2006)"},{"issue":"11","key":"9939_CR37","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1109\/71.969123","volume":"12","author":"I Stojmenovic","year":"2001","unstructured":"Stojmenovic, I., Lin, X.: Power-aware localized routing in wireless networks. IEEE Trans. Parallel Distrib. Syst. 12(11), 1122\u20131133 (2001)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"4","key":"9939_CR38","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/S009753979628292X","volume":"28","author":"I Suzuki","year":"1999","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."},{"issue":"26\u201328","key":"9939_CR39","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1016\/j.tcs.2010.01.037","volume":"411","author":"M Yamashita","year":"2010","unstructured":"Yamashita, M., Suzuki, I.: Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theor. Comput. Sci. 411(26\u201328), 2433\u20132453 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9939_CR40","doi-asserted-by":"crossref","unstructured":"Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced cpu energy. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 374\u2013382 (1995)","DOI":"10.1109\/SFCS.1995.492493"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9939-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9939-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9939-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:14Z","timestamp":1559137514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9939-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,9]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9939"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9939-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,9]]}}}