{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:30:37Z","timestamp":1761597037945},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540416951"},{"type":"electronic","value":"9783540446934"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44693-1_11","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T05:10:18Z","timestamp":1181625018000},"page":"121-131","source":"Crossref","is-referenced-by-count":96,"title":["On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs"],"prefix":"10.1007","author":[{"given":"Andrea E. F.","family":"Clementi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pilu","family":"Crescenzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Penna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianluca","family":"Rossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paola","family":"Vocca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,3,16]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation-Combinatorial optimization problems and their approximability properties. Springer Verlag, 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0022-0000(92)90042-H","volume":"45","author":"R. Bar-Yehuda","year":"1992","unstructured":"R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time complexity of broadcast operations in multi-hop radio networks: an exponential gap between determinism and randomization. J. Computer and Systems Science, 45:104\u2013126, 1992.","journal-title":"J. Computer and Systems Science"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/0222055","volume":"22","author":"R. Bar-Yehuda","year":"1993","unstructured":"R. Bar-Yehuda, A. Israeli, and A. Itai. Multiple communication in multi-hop radio networks. SIAM J. on Computing, 22:875\u2013887, 1993.","journal-title":"SIAM J. on Computing"},{"key":"11_CR4","unstructured":"D. P. Bovet and P. Crescenzi. Introduction to the Theory of Complexity. Prentice Hall, 1994."},{"key":"11_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/3-540-45253-2_14","volume-title":"Proc. 8th Annual European Symposium on Algorithms","author":"A.E.F. Clementi","year":"2000","unstructured":"A.E.F. Clementi, A. Ferreira, P. Penna, S. Perennes, and R. Silvestri. The minimum range assignment problem on linear radio networks. In Proc. 8th Annual European Symposium on Algorithms, volume 1879 of LNCS, pages 143\u2013154, 2000."},{"key":"11_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/978-3-540-48413-4_21","volume-title":"Proc. of Randomization, Approximation and Combinatorial Optimization","author":"A.E.F. Clementi","year":"1999","unstructured":"A.E.F. Clementi, P. Penna, and R. Silvestri. Hardness results for the power range assignment problem in packet radio networks. In Proc. of Randomization, Approximation and Combinatorial Optimization, volume 1671 of LNCS, pages 197\u2013208, 1999. Full version available as ECCC Report TR00-54."},{"key":"11_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1007\/3-540-46541-3_54","volume-title":"Proc. 17th Annual Symposium on Theoretical Aspects of Computer Science","author":"A.E.F. Clementi","year":"2000","unstructured":"A.E.F. Clementi, P. Penna, and R. Silvestri. The power range assignment problem in radio networks on the plane. In Proc. 17th Annual Symposium on Theoretical Aspects of Computer Science, volume 1770 of LNCS, pages 651\u2013660, 2000. Full version available as ECCC Report TR00-54."},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"J.H. Conway and N.J.A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, 1988.","DOI":"10.1007\/978-1-4757-2016-7"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"B. Dixon, M. Rauch, and R.E. Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput., 21:1184\u20131192, 1992.","journal-title":"SIAM J. Comput"},{"key":"11_CR10","unstructured":"A. Ephremides. Complicating factors for the use of distributed algorithms in wireless networks. In 1st Int. Workshop on Approximation and Randomized Algorithms in Communication Networks, invited talk, 2000."},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jagm.1994.1033","volume":"17","author":"D. Eppstein","year":"1994","unstructured":"D. Eppstein. Offline algorithms for dynamic minimum spanning tree problem. J. of Algorithms, 17:237\u2013250, 1994.","journal-title":"J. of Algorithms"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Z. Haas and S. Tabrizi. On some challenges and design choices in ad hoc communications. In Proc. IEEE MILCOM\u201998, 1998.","DOI":"10.1109\/MILCOM.1998.722569"},{"issue":"1","key":"11_CR13","first-page":"3","volume":"14","author":"G.A. Kabatiansky","year":"1978","unstructured":"G.A. Kabatiansky and V.I. Levenshtein. Bounds for packings on a sphere and in space (in russian). Problemy Peredachi Informatsii, 14(1):3\u201325, 1978. English translation: Problems of Information Theory, 14(1):1-17, 1978.","journal-title":"Problemy Peredachi Informatsii"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0304-3975(98)00223-0","volume":"243","author":"L.M. Kirousis","year":"2000","unstructured":"L.M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc. Power consumption in packet radio networks. Theoretical Computer Science, 243:289\u2013306, 2000.","journal-title":"Theoretical Computer Science"},{"key":"11_CR15","unstructured":"G.S. Lauer. Packet radio routing, chapter 11. Prentice-Hall, 1995."},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01262051","volume":"2","author":"R. Mathar","year":"1996","unstructured":"R. Mathar and J. Mattfeldt. Optimal transmission ranges for mobile communication in linear multi-hop packet radio networks. Wireless Networks, 2:329\u2013342, 1996.","journal-title":"Wireless Networks"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C. Monma","year":"1992","unstructured":"C. Monma and S. Suri. Transitions in geometric minimum spanning tree. Discrete and Computational Geometry, 8:265\u2013293, 1992.","journal-title":"Discrete and Computational Geometry"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"E. Nardelli, G. Proietti, and P. Widmayer. Maintainig a minimum spanning tree under transient node failures. In Proc. 8th Annual European Symposium on Algorithms, to appear, 2000.","DOI":"10.1007\/3-540-45253-2_32"},{"key":"11_CR19","unstructured":"K. Pahlavan and A. Levesque. Wireless information networks. Wiley-Interscience, 1995."},{"key":"11_CR20","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994."},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"1490","DOI":"10.1109\/18.133276","volume":"37","author":"P. Piret","year":"1991","unstructured":"P. Piret. On the connectivity of radio networks. IEEE Trans. on Inform. Theory, 37:1490\u20131492, 1991.","journal-title":"IEEE Trans. on Inform. Theory"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1109\/49.329336","volume":"12","author":"D. Raychaudhuri","year":"1994","unstructured":"D. Raychaudhuri and N.D. Wilson. ATM-based transport architecture for multiservices wireless personal communication networks. IEEE J. Selected Areas in Communications, 12:1401\u20131414, 1994.","journal-title":"IEEE J. Selected Areas in Communications"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra. A sub-constant error-probability low-degree test, and sub-constant error-probability pcp characterization of np. In Proc. 29th Ann. ACM Symp. on Theory of Comp., pages 784\u2013798, 1997.","DOI":"10.1145\/258533.258641"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1109\/26.681417","volume":"46","author":"S. Ulukus","year":"1996","unstructured":"S. Ulukus and R.D. Yates. Stocastic power control for cellular radio systems. IEEE Trans. Comm., 46:784\u2013798, 1996.","journal-title":"IEEE Trans. Comm"},{"key":"11_CR25","first-page":"1061","volume":"44","author":"A.D. Wyner","year":"1965","unstructured":"A.D. Wyner. Capabilities of bounded discrepancy decoding. BSTJ, 44:1061\u20131122, 1965.","journal-title":"BSTJ"}],"container-title":["Lecture Notes in Computer Science","STACS 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44693-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T01:29:50Z","timestamp":1556501390000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44693-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540416951","9783540446934"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-44693-1_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}