{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:49:10Z","timestamp":1742384950692},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"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":[[2007,12,6]]},"DOI":"10.1007\/s00453-007-9077-7","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T15:42:07Z","timestamp":1192203727000},"page":"318-336","source":"Crossref","is-referenced-by-count":10,"title":["Improved Approximation Results for the Minimum Energy Broadcasting Problem"],"prefix":"10.1007","volume":"49","author":[{"given":"Michele","family":"Flammini","sequence":"first","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]},{"given":"Alfredo","family":"Navarra","sequence":"additional","affiliation":[]},{"given":"Stephane","family":"Perennes","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9077_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/978-3-540-39658-1_13","volume-title":"Proceedings of the 11th Annual European Symposium on Algorithms (ESA)","author":"G. Calinescu","year":"2003","unstructured":"Calinescu, G., Kapoor, S., Olshevsky, A., Zelikovsky, A.: Network lifetime and power assignment in ad-hoc wireless networks. In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2832, pp. 114\u2013126. Springer, New York (2003)"},{"key":"9077_CR2","first-page":"119","volume-title":"Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science","author":"G. Calinescu","year":"2002","unstructured":"Calinescu, G., Mandoiu, I., Zelikovsky, A.: Symmetric connectivity with minimum power consumption in radio networks. In: Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science, pp. 119\u2013130. Kluwer, Dordrecht (2002)"},{"key":"9077_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/3-540-36136-7_30","volume-title":"Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC)","author":"I. Caragiannis","year":"2002","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: New results for energy-efficient broadcasting in wireless networks. In: Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 2518, pp. 332\u2013343. Springer, New York (2002)"},{"key":"9077_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/978-3-540-24587-2_60","volume-title":"Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC)","author":"I. Caragiannis","year":"2003","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Energy-efficient wireless network design. In: Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 2906, pp. 585\u2013594. Springer, New York (2003)"},{"key":"9077_CR5","first-page":"2210","volume-title":"Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)","author":"J. Cartigny","year":"2003","unstructured":"Cartigny, J., Simplot, D., Stojmenovic, I.: Localized minimum-energy broadcasting in ad-hoc networks. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 3, pp. 2210\u20132217. IEEE Computer Society, Los Alamitos (2003)"},{"issue":"3","key":"9077_CR6","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1109\/26.20105","volume":"37","author":"W. Chen","year":"1989","unstructured":"Chen, W., Huang, N.: The strongly connecting problem on multihop packet radio networks. IEEE Trans. Commun. 37(3), 293\u2013295 (1989)","journal-title":"IEEE Trans. Commun."},{"key":"9077_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-44693-1_11","volume-title":"Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"A. Clementi","year":"2001","unstructured":"Clementi, A., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the complexity of computing minimum energy consumption broadcast subgraphs. In: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 2010, pp. 121\u2013131. Springer, New York (2001)"},{"key":"9077_CR8","first-page":"222","volume-title":"Proceedings of the 3rd IEEE IPDPS Workshop on Wireless, Mobile and Ad Hoc Networks (WMAN)","author":"A. Clementi","year":"2003","unstructured":"Clementi, A., Huiban, G., Penna, P., Rossi, G., Verhoeven, Y.C.: On the approximation ratio of the MST-based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks. In: Proceedings of the 3rd IEEE IPDPS Workshop on Wireless, Mobile and Ad Hoc Networks (WMAN), p. 222. IEEE Computer Society, Los Alamitos (2003)"},{"key":"9077_CR9","volume-title":"Sphere Packings, Lattices, and Groups","author":"J.H. Conway","year":"1998","unstructured":"Conway, J.H., Sloane, N.J.A.: The kissing number problem. Bounds on kissing numbers. In: Sphere Packings, Lattices, and Groups, 3rd edn. Springer, New York (1998), Chaps.\u00a02.1 and\u00a013","edition":"3"},{"key":"9077_CR10","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1145\/1062689.1062744","volume-title":"Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)","author":"Q. Dong","year":"2005","unstructured":"Dong, Q., Banerjee, S., Adler, M., Misra, A.: Minimum energy reliable paths using unreliable wireless links. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 449\u2013459. ACM Press, New York (2005)"},{"issue":"3","key":"9077_CR11","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/581291.581300","volume":"6","author":"S. Doshi","year":"2002","unstructured":"Doshi, S., Bhandare, S., Brown, T.X.: An on-demand minimum energy routing protocol for a wireless ad hoc network. SIGMOBILE Mob. Comput. Commun. Rev. 6(3), 50\u201366 (2002)","journal-title":"SIGMOBILE Mob. Comput. Commun. Rev."},{"key":"9077_CR12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimal branchings. J. Res. Nat. Bur. Stand. B 71, 233\u2013240 (1967)","journal-title":"J. Res. Nat. Bur. Stand. B"},{"key":"9077_CR13","first-page":"85","volume-title":"Proceedings of ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC)","author":"M. Flammini","year":"2004","unstructured":"Flammini, M., Klasing, R., Navarra, A., Perennes, S.: Improved approximation results for the minimum energy broadcasting problem. In: Proceedings of ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 85\u201391. ACM Press, New York (2004)"},{"key":"9077_CR14","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF02125348","volume":"9","author":"A.M. Frieze","year":"1989","unstructured":"Frieze, A.M., McDiarmid, C.J.H.: On random minimum length spanning trees. Combinatorica 9, 363\u2013374 (1989)","journal-title":"Combinatorica"},{"key":"9077_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E. Gilbert","year":"1968","unstructured":"Gilbert, E., Pollak, H.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1\u201329 (1968)","journal-title":"SIAM J. Appl. Math."},{"key":"9077_CR16","doi-asserted-by":"crossref","DOI":"10.1002\/0470867388","volume-title":"Wireless Sensor Network Designs","author":"A. Hac","year":"2003","unstructured":"Hac, A.: Wireless Sensor Network Designs. Wiley, New York (2003)"},{"issue":"1\u20132","key":"9077_CR17","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/S0304-3975(98)00223-0","volume":"243","author":"L. Kirousis","year":"2000","unstructured":"Kirousis, L., Kranakis, E., Krizanc, D., Pelc, A.: Power consumption in packet radio networks. Theor. Comput. Sci. 243(1\u20132), 289\u2013305 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9077_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1007\/978-3-540-24693-0_71","volume-title":"Proceedings of the 3rd IFIP-TC6 International Networking Conference","author":"R. Klasing","year":"2004","unstructured":"Klasing, R., Navarra, A., Papadopoulos, A., Perennes, S.: Adaptive broadcast consumption (ABC), a new heuristic and new bounds for the minimum energy broadcast routing problem. In: Proceedings of the 3rd IFIP-TC6 International Networking Conference. Lecture Notes in Computer Science, vol.\u00a03042, pp. 866\u2013877. Springer, New York (2004)"},{"issue":"4","key":"9077_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1145\/509506.509518","volume":"5","author":"X. Li","year":"2001","unstructured":"Li, X., Wan, P.: Constructing minimum energy mobile wireless networks. SIGMOBILE Mob. Comput. Commun. Rev. 5(4), 55\u201367 (2001)","journal-title":"SIGMOBILE Mob. Comput. Commun. Rev."},{"key":"9077_CR20","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1145\/513800.513815","volume-title":"Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)","author":"W. Liang","year":"2002","unstructured":"Liang, W.: Constructing minimum-energy broadcast trees in wireless ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 112\u2013122. ACM Press, New York (2002)"},{"key":"9077_CR21","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/1023756.1023769","volume-title":"Proceedings of the 1st ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN)","author":"P. Penna","year":"2004","unstructured":"Penna, P., Ventre, C.: Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees. In: Proceedings of the 1st ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN), pp. 61\u201368. ACM Press, New York (2004)"},{"key":"9077_CR22","volume-title":"Wireless Communications: Principles and Practice","author":"T. Rappaport","year":"1996","unstructured":"Rappaport, T.: Wireless Communications: Principles and Practice. Prentice-Hall, Englewood Cliffs (1996)"},{"issue":"6","key":"9077_CR23","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1023\/A:1020381720601","volume":"8","author":"P.J. Wan","year":"2002","unstructured":"Wan, P.J., Calinescu, G., Li, X., Frieder, O.: Minimum energy broadcast routing in static ad hoc wireless networks. Wirel. Netw. 8(6), 607\u2013617 (2002)","journal-title":"Wirel. Netw."},{"key":"9077_CR24","first-page":"585","volume-title":"Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)","author":"J.E. Wieselthier","year":"2000","unstructured":"Wieselthier, J.E., Nguyen, G.D., Ephremides, A.: On the construction of energy-efficient broadcast and multicast trees in wireless networks. In: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 585\u2013594. IEEE Computer Society, Los Alamitos (2000)"},{"key":"9077_CR25","first-page":"172","volume-title":"Proceedings of the 8th Annual International Conference on Mobile Computing and Networking (MobiCom)","author":"M. Zagalj","year":"2002","unstructured":"Zagalj, M., Hubaux, J., Enz, C.: Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues. In: Proceedings of the 8th Annual International Conference on Mobile Computing and Networking (MobiCom), pp. 172\u2013182. ACM Press, New York (2002)"},{"key":"9077_CR26","volume-title":"Wireless Sensor Networks: An Information Processing Approach","author":"F. Zhao","year":"2004","unstructured":"Zhao, F., Guibas, L.: Wireless Sensor Networks: An Information Processing Approach. Kaufmann, Los Altos (2004)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9077-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9077-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9077-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9077-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,12,6]]}},"alternative-id":["9077"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9077-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,13]]}}}