{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:39Z","timestamp":1763467779797,"version":"3.32.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,12,14]],"date-time":"2006-12-14T00:00:00Z","timestamp":1166054400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2007,3,12]]},"DOI":"10.1007\/s10107-006-0057-5","type":"journal-article","created":{"date-parts":[[2006,12,13]],"date-time":"2006-12-13T10:24:29Z","timestamp":1166005469000},"page":"195-208","source":"Crossref","is-referenced-by-count":32,"title":["Power optimization for connectivity problems"],"prefix":"10.1007","volume":"110","author":[{"given":"Mohammad T.","family":"Hajiaghayi","sequence":"first","affiliation":[]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[]},{"given":"Vahab S.","family":"Mirrokni","sequence":"additional","affiliation":[]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,12,14]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","unstructured":"Althaus, E., Calinescu G., Mandoiu I., Prasad S., Tchervenski, N., Zelikovsky, A.: Power efficient range assignment in ad-hoc wireless networks. In: Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp. 1889\u20131894 (2003)","DOI":"10.1109\/WCNC.2003.1200675"},{"key":"57_CR2","doi-asserted-by":"crossref","unstructured":"Bahramgiri, M., Hajiaghayi, M., Mirrokni, V.: Fault-tolerant and 3-dimensional distributed topology control algorithms wireless multi-hop networks. In: Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (ICCCN), IEEE Press, pp. 392\u2013398 (2002)","DOI":"10.1109\/ICCCN.2002.1043097"},{"key":"57_CR3","doi-asserted-by":"crossref","unstructured":"Blough, D.M., Leoncini, M., Resta, G., Santi, P.: On the symmetric range assignment problem in wireless ad hoc networks. In: TCS \u201902: Proceedings of the IFIP 17th World Computer Congress\u2014TC1 Stream\/2nd IFIP International Conference on Theoretical Computer Science, Kluwer, The Netherlands, pp. 71\u201382 (2002)","DOI":"10.1007\/978-0-387-35608-2_7"},{"key":"57_CR4","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Mandoiu, I.I., Zelikovsky, A.: Symmetric connectivity with minimum power consumption in radio networks. In: TCS \u201902: Proceedings of the IFIP 17th World Computer Congress\u2014TC1 Stream\/2nd IFIP International Conference on Theoretical Computer Science, Kluwer, The Newtherlands, pp. 119\u2013130 (2002)","DOI":"10.1007\/978-0-387-35608-2_11"},{"key":"57_CR5","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Wan, P.-J.: Range assignment for high connectivity in wireless ad hoc network. In: Adhoc-Now, pp. 235\u2013246 (2003)","DOI":"10.1007\/978-3-540-39611-6_21"},{"key":"57_CR6","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1006\/jagm.1999.1040","volume":"33","author":"J. Cheriyan","year":"1999","unstructured":"Cheriyan J. and Thurimella R (1999). Fast algorithms for k-shredders and k-node connectivity augmentation. J. Algorithms 33: 15\u201350","journal-title":"J. Algorithms"},{"key":"57_CR7","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Vempala, S., Vetta, A.: An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM J. Comput. 32, 1050\u20131055 (electronic) (2003)","DOI":"10.1137\/S0097539701392287"},{"key":"57_CR8","unstructured":"Clementi, A., Huiban, G., Penna, P., Rossi, G., Verhoeven, Y.: Some recent theoretical advances and open questions on energy consumption in ad-hoc wireless networks. Manuscript 23\u201338 (2002)"},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"Clementi, A.E.F., Penna, P., Silvestri, R.: Hardness results for the power range assignmet problem in packet radio networks. In: RANDOM-APPROX \u201999: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Springer, Berlin Heidelberg New York, pp. 197\u2013208 (1999)","DOI":"10.1007\/978-3-540-48413-4_21"},{"issue":"115","key":"57_CR10","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0024-3795(89)90469-2","volume":"114","author":"A. Frank","year":"1989","unstructured":"Frank A. and Tardos \u00c9. (1989). An application of submodular flows. Linear Algebra Appl. 114(115): 329\u2013348","journal-title":"Linear Algebra Appl."},{"key":"57_CR11","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Immorlica, N., Mirrokni, V.S.: Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. In: MobiCom \u201903: Proceedings of the 9th annual international conference on Mobile computing and networking, ACM Press, pp. 300\u2013312 (2003)","DOI":"10.1145\/938985.939016"},{"key":"57_CR12","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1006\/jagm.1996.0052","volume":"21","author":"S. Khuller","year":"1996","unstructured":"Khuller S. and Raghavachari B. (1996). Improved approximation algorithms for uniform connectivity problems. J. Algorithms 21: 434\u2013450","journal-title":"J. Algorithms"},{"key":"57_CR13","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S. Khuller","year":"1994","unstructured":"Khuller S. and Vishkin U. (1994). Biconnectivity approximations and graph carvings. J. Assoc. Comput. Mach. 41: 214\u2013235","journal-title":"J. Assoc. Comput. Mach."},{"key":"57_CR14","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/S0304-3975(98)00223-0","volume":"243","author":"L.M. Kirousis","year":"2000","unstructured":"Kirousis L.M., Kranakis E., Krizanc D. and Pelc A. (2000). Power consumption in packet radio networks. Theoret. Comput. Sci. 243: 289\u2013305","journal-title":"Theoret. Comput. Sci."},{"key":"57_CR15","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1007\/s00453-001-0021-y","volume":"30","author":"G. Kortsarz","year":"2001","unstructured":"Kortsarz G. (2001). On the hardness of approximating spanners. Algorithmica 30: 432\u2013450","journal-title":"Algorithmica"},{"key":"57_CR16","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00453-003-1027-4","volume":"37","author":"G. Kortsarz","year":"2003","unstructured":"Kortsarz G. and Nutov Z. (2003). Approximating node connectivity problems via set covers. Algorithmica 37: 75\u201392","journal-title":"Algorithmica"},{"key":"57_CR17","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Approximation algorithm for k-node connected subgraphs via critical graphs. In: STOC \u201904: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, ACM Press, pp. 138\u2013145 (2003)","DOI":"10.1145\/1007352.1007381"},{"key":"57_CR18","doi-asserted-by":"crossref","unstructured":"Li, L., Halpern, J.Y., Bahl, P., Wang, Y.-M., Wattenhofer, R.: Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. In: PODC \u201901: Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, ACM Press, pp. 264\u2013273 (2001)","DOI":"10.1145\/383962.384043"},{"key":"57_CR19","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1023\/B:MONE.0000048543.95178.f5","volume":"10","author":"E.L. Lloyd","year":"2005","unstructured":"Lloyd E.L., Liu R., Marathe M.V., Ramanathan R. and Ravi S.S. (2005). Algorithmic aspects of topology control problems for ad hoc networks. Mob. Netw. Appl. 10: 19\u201334","journal-title":"Mob. Netw. Appl."},{"key":"57_CR20","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01304873","volume":"23","author":"W. Mader","year":"1972","unstructured":"Mader W. (1972). Ecken vom grad n in minimalen n-fach zusammenhangenden Graphen. Arch. Math. (Basel) 23: 219\u2013224","journal-title":"Arch. Math. (Basel)"},{"key":"57_CR21","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"J.B. Orlin","year":"1993","unstructured":"Orlin J.B. (1993). A faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41: 338\u2013350","journal-title":"Oper. Res."},{"key":"57_CR22","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou C.H. and Yannakakis M. (1991). Optimization. approximation and complexity classes. J. Comput. Syst. Sci. 43: 425\u2013440","journal-title":"J. Comput. Syst. Sci."},{"key":"57_CR23","doi-asserted-by":"crossref","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27, 763\u2013803 (electronic) (1998)","DOI":"10.1137\/S0097539795280895"},{"key":"57_CR24","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1109\/49.779917","volume":"17","author":"V. Rodoplu","year":"1999","unstructured":"Rodoplu V. and Meng T.H. (1999). Minimum energy mobile wireless networks. IEEE J. Select. Areas Commun. 17: 1333\u20131344","journal-title":"IEEE J. Select. Areas Commun."},{"key":"57_CR25","doi-asserted-by":"crossref","unstructured":"Wattenhofer, R., Li, L., Bahl, V., Wang, Y.: Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In: Proceedings of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), IEEE Press, pp. 1388\u20131397 (2001)","DOI":"10.1109\/INFCOM.2001.916634"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0057-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-006-0057-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0057-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T09:28:41Z","timestamp":1736674121000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-006-0057-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12,14]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3,12]]}},"alternative-id":["57"],"URL":"https:\/\/doi.org\/10.1007\/s10107-006-0057-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2006,12,14]]}}}