{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:59:29Z","timestamp":1725559169620},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540261995"},{"type":"electronic","value":"9783540321026"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11496915_26","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T12:40:39Z","timestamp":1279111239000},"page":"349-361","source":"Crossref","is-referenced-by-count":10,"title":["Power Optimization for Connectivity Problems"],"prefix":"10.1007","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","reference":[{"key":"26_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":"26_CR2","first-page":"392","volume-title":"Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (ICCCN)","author":"M. Bahramgiri","year":"2002","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), pp. 392\u2013398. IEEE Press, Los Alamitos (2002)"},{"key":"26_CR3","first-page":"71","volume-title":"TCS 2002: Proceedings of the IFIP 17th World Computer Congress - TC1 Stream \/ 2nd IFIP International Conference on Theoretical Computer Science","author":"D.M. Blough","year":"2002","unstructured":"Blough, D.M., Leoncini, M., Resta, G., Santi, P.: On the symmetric range assignment problem in wireless ad hoc networks. In: TCS 2002: Proceedings of the IFIP 17th World Computer Congress - TC1 Stream \/ 2nd IFIP International Conference on Theoretical Computer Science, pp. 71\u201382. Kluwer, B.V. (2002)"},{"key":"26_CR4","first-page":"119","volume-title":"TCS 2002: Proceedings of the IFIP 17th World Computer Congress - TC1 Stream \/ 2nd IFIP International Conference on Theoretical Computer Science","author":"G. Calinescu","year":"2002","unstructured":"Calinescu, G., Mandoiu, I.I., Zelikovsky, A.: Symmetric connectivity with minimum power consumption in radio networks. In: TCS 2002: Proceedings of the IFIP 17th World Computer Congress - TC1 Stream \/ 2nd IFIP International Conference on Theoretical Computer Science, pp. 119\u2013130. Kluwer Academic Publishers, B.V. (2002)"},{"key":"26_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":"26_CR6","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1006\/jagm.1999.1040","volume":"33","author":"J. Cheriyan","year":"1999","unstructured":"Cheriyan, J., Thurimella, R.: Fast algorithms for k-shredders and k-node connectivity augmentation. J. Algorithms\u00a033, 15\u201350 (1999)","journal-title":"J. Algorithms"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1137\/S0097539701392287","volume":"32","author":"J. Cheriyan","year":"2003","unstructured":"Cheriyan, J., Vempala, S., Vetta, A.: An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM J. Comput.\u00a032, 1050\u20131055 (2003) (electronic)","journal-title":"SIAM J. Comput."},{"key":"26_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, pp. 23\u201338 (2002)"},{"key":"26_CR9","first-page":"197","volume-title":"RANDOM-APPROX 1999: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems","author":"A.E.F. Clementi","year":"1999","unstructured":"Clementi, A.E.F., Penna, P., Silvestri, R.: Hardness results for the power range assignmet problem in packet radio networks. In: RANDOM-APPROX 1999: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 197\u2013208. Springer, Heidelberg (1999)"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0024-3795(89)90469-2","volume":"114\/115","author":"A. Frank","year":"1989","unstructured":"Frank, A., Tardos, \u00c9.: An application of submodular flows. Linear Algebra Appl.\u00a0114\/115, 329\u2013348 (1989)","journal-title":"Linear Algebra Appl."},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/938985.939016","volume-title":"MobiCom 2003: Proceedings of the 9th annual international conference on Mobile computing and networking","author":"M. Hajiaghayi","year":"2003","unstructured":"Hajiaghayi, M., Immorlica, N., Mirrokni, V.S.: Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. In: MobiCom 2003: Proceedings of the 9th annual international conference on Mobile computing and networking, pp. 300\u2013312. ACM Press, New York (2003)"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1006\/jagm.1996.0052","volume":"21","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B.: Improved approximation algorithms for uniform connectivity problems. J. Algorithms\u00a021, 434\u2013450 (1996)","journal-title":"J. Algorithms"},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J. Assoc. Comput. Mach.\u00a041, 214\u2013235 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"26_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":"Kirousis, L.M., Kranakis, E., Krizanc, D., Pelc, A.: Power consumption in packet radio networks. Theoret. Comput. Sci.\u00a0243, 289\u2013305 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"26_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.: On the hardness of approximating spanners. Algorithmica\u00a030, 432\u2013450 (2001)","journal-title":"Algorithmica"},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00453-003-1027-4","volume":"37","author":"G. Kortsarz","year":"2003","unstructured":"Kortsarz, G., Nutov, Z.: Approximating node connectivity problems via set covers. Algorithmica\u00a037, 75\u201392 (2003)","journal-title":"Algorithmica"},{"key":"26_CR17","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1145\/1007352.1007381","volume-title":"STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing","author":"G. Kortsarz","year":"2004","unstructured":"Kortsarz, G., Nutov, Z.: Approximation algorithm for k-node connected subgraphs via critical graphs. In: STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 138\u2013145. ACM Press, New York (2004)"},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/383962.384043","volume-title":"PODC 2001: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing","author":"L. Li","year":"2001","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 2001: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, pp. 264\u2013273. ACM Press, New York (2001)"},{"key":"26_CR19","doi-asserted-by":"publisher","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., Ravi, S.S.: Algorithmic aspects of topology control problems for ad hoc networks. Mob. Netw. Appl.\u00a010, 19\u201334 (2005)","journal-title":"Mob. Netw. Appl."},{"key":"26_CR20","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01304873","volume":"23","author":"W. Mader","year":"1972","unstructured":"Mader, W.: Ecken vom grad n in minimalen n-fach zusammenhangenden Graphen. Arch. Math (Basel)\u00a023, 219\u2013224 (1972)","journal-title":"Arch. Math. (Basel)"},{"key":"26_CR21","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"J.B. Orlin","year":"1993","unstructured":"Orlin, J.B.: A faster strongly polynomial minimum cost flow algorithm. Oper. Res.\u00a041, 338\u2013350 (1993)","journal-title":"Oper. Res."},{"key":"26_CR22","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. J. Comput. System Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput.\u00a027, 763\u2013803 (1998) (electronic)","journal-title":"SIAM J. Comput."},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1109\/49.779917","volume":"17","author":"V. Rodoplu","year":"1999","unstructured":"Rodoplu, V., Meng, T.H.: Minimum energy mobile wireless networks. IEEE J. Selected Areas in Communications\u00a017, 1333\u20131344 (1999)","journal-title":"IEEE J. Selected Areas in Communications"},{"key":"26_CR25","first-page":"1388","volume-title":"Proceedings of twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)","author":"R. Wattenhofer","year":"2001","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), pp. 1388\u20131397. IEEE Press, Los Alamitos (2001)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11496915_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:40:22Z","timestamp":1619491222000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11496915_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540261995","9783540321026"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11496915_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}