{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T02:14:33Z","timestamp":1743128073192,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"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_13","type":"book-chapter","created":{"date-parts":[[2009,11,17]],"date-time":"2009-11-17T11:17:06Z","timestamp":1258456626000},"page":"335-355","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks"],"prefix":"10.1007","author":[{"given":"Alfredo","family":"Navarra","sequence":"first","affiliation":[]},{"given":"Ioannis","family":"Caragiannis","sequence":"additional","affiliation":[]},{"given":"Michele","family":"Flammini","sequence":"additional","affiliation":[]},{"given":"Christos","family":"Kaklamanis","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,9]]},"reference":[{"key":"13_CR1","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 32nd International Colloquium on Automata, Languages and Programming (ICALP), LNCS 3580, Springer, pp. 1139\u20131150, 2005","DOI":"10.1007\/11523468_92"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Athanassopoulos, S., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Experimental comparison of algorithms for energy-efficient multicasting in ad hoc networks. In: Proceedings of the 3rd International Conference on Ad Hoc Networks & Wireless (ADHOC NOW), LNCS 3158, Springer, pp. 183-196, 2004","DOI":"10.1007\/978-3-540-28634-9_15"},{"issue":"1","key":"13_CR3","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"G. Ausiello","year":"1980","unstructured":"Ausiello, G., D\u2019Atri, A., Protasi, M.: Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences, 21(1):136\u2013153, 1980","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Barsi, F., Navarra, A., Pinotti, M. C.: Cheapest Path in Multi-Interface Networks. In: Proceedings of the 10th International Conference on Distributed Computing and Networking (ICDCN), LNCS, Springer, 2009","DOI":"10.1007\/978-3-540-92295-7_7"},{"issue":"1-3","key":"13_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/j.tcs.2006.09.004","volume":"369","author":"V. Bil\u00f3","year":"2006","unstructured":"Bil\u00f3, V., Flammini, M., Melideo, G., Moscardelli, L., Navarra, A.: Sharing the cost of multicast transmissions in euclidean and general wireless networks. Theoretical Computer Science, 369(1-3):269\u2013284, 2006","journal-title":"Theoretical Computer Science"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R. L. Brooks","year":"1941","unstructured":"Brooks, R. L.: On coloring the nodes of a network. In: Proceedings of Cambridge Philosophical Society, 37:194\u2013197, 1941","journal-title":"Proceedings of Cambridge Philosophical Society"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"\u010cagalj, 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), ACM Press, pp. 172\u2013182, 2002","DOI":"10.1145\/570645.570667"},{"issue":"3","key":"13_CR8","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10878-005-1409-4","volume":"9","author":"H. Cai","year":"2005","unstructured":"Cai, H., Zhao, Y.: On approximation ratios of minimum-energy multicast routing in wireless networks. Journal of Combinatorial Optimization, 9(3):243\u2013262, 2005","journal-title":"Journal of Combinatorial Optimization"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Kapoor, S., Olshevsky, A., Zelikovsky, A.: Network lifetime and power assignment in adhoc wireless networks. In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA), LNCS 2832, Springer, pp. 114\u2013126, 2003","DOI":"10.1007\/978-3-540-39658-1_13"},{"issue":"12","key":"13_CR10","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1109\/TSE.2003.1265521","volume":"29","author":"M. Caporuscio","year":"2003","unstructured":"Caporuscio, M., Carzaniga, A., Wolf, A. L.: Design and evaluation of a support service for mobile, wireless publish\/subscribe applications. IEEE Transactions on Software Engineering, 29(12):1059\u20131071, 2003","journal-title":"IEEE Transactions on Software Engineering"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Caporuscio, M., Charlet, D., Issarny, V., Navarra, A.: Energetic Performance of Service-oriented Multi-radio Networks: Issues and Perspectives. In: Proceedings of the 6th International Workshop on Software and Performance (WOSP), pp. 42\u201345. ACM Press, 2007","DOI":"10.1145\/1216993.1217002"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Flammini, M., Moscardelli, L.: An exponential improvement on the mst heuristic for minimum energy broadcasting in ad hoc wireless networks. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 4596, Springer, pp. 447\u2013458, 2007","DOI":"10.1007\/978-3-540-73420-8_40"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: New results for energy-efficient broadcasting in wireless networks. In: Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC), LNCS 2518, Springer, pp. 332\u2013343, 2002","DOI":"10.1007\/3-540-36136-7_30"},{"issue":"3","key":"13_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0020-0190(02)00484-2","volume":"86","author":"I. Caragiannis","year":"2003","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem. Information Processing Letters, 86(3):149\u2013154, 2003","journal-title":"Information Processing Letters"},{"issue":"5","key":"13_CR15","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00224-005-1204-8","volume":"39","author":"I. Caragiannis","year":"2006","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Energy-efficient wireless network design. Theory of Computing Systems, 39(5), pp. 593\u2013617, 2006","journal-title":"Theory of Computing Systems"},{"key":"13_CR16","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, IEEE Computer Society Press, pp. 2210\u20132217, 2003"},{"issue":"3","key":"13_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233\u2013235, 1979","journal-title":"Mathematics of Operations Research"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Cilibrasi, R., Lotker, Z., Navarra, A., Perennes, S., Vitanyi, P.: About the lifespan of peer to peer networks. In: Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS), LNCS 4305, Springer, pp. 290\u2013304, 2006","DOI":"10.1007\/11945529_21"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Clementi, A. E. F., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the complexity of computing minimum energy consumption broadcast subgraph. In: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 2010, Springer, pp. 121\u2013131, 2001","DOI":"10.1007\/3-540-44693-1_11"},{"issue":"1-3","key":"13_CR20","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1016\/S0304-3975(02)00538-8","volume":"299","author":"A. E. F. Clementi","year":"2003","unstructured":"Clementi, A. E. F., Di Ianni, M., Silvestri, R.: The minimum broadcast range assignment problem on linear multi-hop wireless networks. Theoretical Computer Science, 299(1-3):751\u2013761, 2003","journal-title":"Theoretical Computer Science"},{"key":"13_CR21","volume-title":"\u201cThe Kissing Number Problem\u201d and \u201cBounds on Kissing Numbers\u201d.","author":"J. H. Conway","year":"1998","unstructured":"Conway, J. H., Sloane, N. J. A.: \u201cThe Kissing Number Problem\u201d and \u201cBounds on Kissing Numbers\u201d. Ch. 2.1 and Ch. 13 in: Sphere Packings, Lattices, and Groups. Springer-Verlag, New York, 3rd edition, 1998","edition":"3"},{"key":"13_CR22","first-page":"1001","volume":"2","author":"A. K. Das","year":"2003","unstructured":"Das, A. K., Markas, R. J., El-Sharkawai, M., Arabshahi, P., Gray, A.: Minimum energy broadcast trees for wireless networks: Integer programming formulations. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), IEEE Computer Society, Vol. 2, pp. 1001\u20131010. 2003","journal-title":"IEEE Computer Society"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Farag\u00f3, A., Basagni, S.: The Effect of Multi-Radio Nodes on Network Connectivity\u2014A Graph Theoretic Analysis. In: Proceedings of the 19th International IEEE Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), 2008","DOI":"10.1109\/PIMRC.2008.5173153"},{"key":"13_CR24","doi-asserted-by":"crossref","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, 2004","DOI":"10.1145\/1022630.1022644"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Flammini, M., Klasing, R., Navarra, A., Perennes, S.: Tightening the upper bound for the Minimum Energy Broadcasting. Wireless Networks, Vol. 14(5), pp. 959-669, 2008","DOI":"10.1007\/s11276-006-0007-4"},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Flammini, M., Navarra, A., Perennes, S.: The \u201creal\u201d approximation factor of the MST heuristic for the minimum energy broadcasting. ACM Journal of Experimental Algorithmics, 11, 2006. Preliminary version in: Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA), LNCS 3503, Springer, pp. 22\u201331, 2005","DOI":"10.1145\/1187436.1216587"},{"key":"13_CR27","doi-asserted-by":"publisher","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"},{"issue":"1","key":"13_CR28","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. Information and Computation, 150(1), pp. 57\u201374, 1999","journal-title":"Information and Computation"},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Hac, A.: Wireless sensor network designs. John Wiley & Sons, Ltd, 2003","DOI":"10.1002\/0470867388"},{"key":"13_CR30","unstructured":"Kang, I., Poovendran, R.: Iterated local optimization for minimum energy broadcast. In: Proceedings of the 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), pp. 332\u2013341, 2005"},{"issue":"4","key":"13_CR31","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/s00453-007-9077-7","volume":"49","author":"R. Klasing","year":"2007","unstructured":"Klasing, R., Flammini, M., Navarra, A., Perennes, S.: Improved approximation results for the Minimum Energy Broadcasting Problem. Algorithmica, 49(4):318\u2013336, 2007","journal-title":"Algorithmica"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Klasing, R., Kosowski, A., Navarra, A.: Cost minimisation in multi-interface networks. In: Proceedings of the 1st EuroFGI International Conference on Network Control and Optimization (NET-COOP), LNCS 4465, Springer, pp. 276\u2013285, 2007","DOI":"10.1007\/978-3-540-72709-5_29"},{"key":"13_CR33","doi-asserted-by":"crossref","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, LNCS 3042, Springer, pp. 866\u2013877, 2004","DOI":"10.1007\/978-3-540-24693-0_71"},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Navarra, A.: Cost minimisation in unbounded multi-interface networks. In: Proceedings of the 2nd PPAM Workshop on Scheduling for Parallel Computing (SPC), Lecture Notes in Computer Science 4967, Springer-Verlag, pp. 1039-1047, 2007","DOI":"10.1007\/978-3-540-68111-3_110"},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Navarra, A., Pinotti, M. C.: Connectivity in Multi-Interface Networks. In: Proceedings of the 4th International Symposium on Trustworthy Global Computing (TGC), LNCS, Springer, 2008","DOI":"10.1007\/978-3-642-00945-7_10"},{"key":"13_CR36","doi-asserted-by":"crossref","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), ACM Press, pp. 112\u2013122, 2002","DOI":"10.1145\/513800.513815"},{"key":"13_CR37","unstructured":"Li, F., Nikolaidis, I.: On minimum-energy broadcasting in all-wireless networks. In: Proceedings of the 26th Annual IEEE Conference on Local Computer Networks (LCN), IEEE Computer Society, p. 193, 2001"},{"issue":"5","key":"13_CR38","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1016\/j.adhoc.2007.06.003","volume":"6","author":"A. Navarra","year":"2008","unstructured":"Navarra, A.: 3-D Minimum Energy Broadcasting problem. Ad Hoc Networks, Vol. 6(5), pp. 734-743, 2008","journal-title":"Ad Hoc Networks"},{"key":"13_CR39","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR40","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Anuual ACM Symposium on Theory of Computing (STOC), pp. 475\u2013484, 1997","DOI":"10.1145\/258533.258641"},{"issue":"6","key":"13_CR41","doi-asserted-by":"publisher","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 broadcasting in static ad hoc wireless networks. Wireless Networks, 8(6):607\u2013617, 2002","journal-title":"Wireless Networks"},{"key":"13_CR42","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), IEEE Computer Society, pp. 585\u2013594, 2000"},{"key":"13_CR43","unstructured":"Yuan, D.: Computing Optimal or Near-Optimal Trees for Minimum-Energy Broadcasting in Wireless Networks. In: Proceedings of the 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), pp. 323\u2013331, 2005"},{"key":"13_CR44","unstructured":"Zhao, F., Guibas, L.: Wireless sensor networks: an information processing approach. Morgan Kaufmann, 2004"},{"key":"13_CR45","unstructured":"Zosin, L., Khuller, S.: On Directed Steiner Trees. In: Proceedings of the 13th Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA), pp. 59-63, 2002"}],"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_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T20:31:44Z","timestamp":1676061104000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02250-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022494","9783642022500"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02250-0_13","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"}}]}}