On minimum power connectivity problems

Althaus, 2006, Power efficient range assignment for symmetric connectivity in static ad-hoc wireless networks, Wireless Networks, 12, 287, 10.1007/s11276-005-5275-x Auletta, 1999, A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph, Journal of Algorithms, 32, 21, 10.1006/jagm.1999.1006 Calinescu, 2003, Network lifetime and power assignment in ad hoc wireless networks, vol. 2832, 114 Calinescu, 2006, Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks, Mobile Networks and Applications, 11, 121, 10.1007/s11036-006-4466-8 Caragiannis, 2006, Energy-efficient wireless network design, Theory of Computing Systems, 39, 593, 10.1007/s00224-005-1204-8 Cheriyan, 2001, On rooted node-connectivity problems, Algorithmica, 30, 353, 10.1007/s00453-001-0017-7 A.E.F. Clementi, P. Penna, R. Silvestri, Hardness results for the power range assignment problem in packet radio networks in: APPROX, 1999, pp. 197–208 Cook, 1998 Dinitz, 1999, A 3-approximation algorithm for finding an optimum 4,5-vertex-connected spanning subgraph, Journal of Algorithms, 32, 31, 10.1006/jagm.1999.1007 Edmonds, 1979, Matroid intersection, Annals of Discrete Mathematics, 185 Feige, 2001, The dense k-subgraph problem, Algorithmica, 29, 410, 10.1007/s004530010050 Frank, 1995, Connectivity and network flows, 111 A. Frank, Rooted k-connections in digraphs, EGRES TR No. 2006-07, 2006 Frank, 1989, An application of submodular flows, Linear Algebra and its Applications, 114/115, 329, 10.1016/0024-3795(89)90469-2 H.N. Gabow, A representation for crossing set families with application to submodular flow problems, in: SODA, 1993, pp. 202–211 M.T. Hajiaghayi, N. Immorlica, V.S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, in: MOBICOM, 2003, pp. 300–312 Hajiaghayi, 2007, Power optimization for connectivity problems, Mathematical Programming, 110, 195, 10.1007/s10107-006-0057-5 Jia, 2005, Power assignment for k-connectivity in wireless ad hoc networks, J. Combin. Optim., 9, 213, 10.1007/s10878-005-6858-2 Khuller, 1995, Approximation algorithms for finding highly connected subgraphs, 236 Khuller, 1994, Biconnectivity approximations and graph carvings, Journal of the Association for Computing Machinery, 41, 214, 10.1145/174652.174654 Kirousis, 2000, Power consumption in packet radio networks, Theoret. Comput. Sci., 243, 289, 10.1016/S0304-3975(98)00223-0 G. Kortsarz, V.S. Mirrokni, Z. Nutov, E. Tsanko, Approximating minimum power degree and connectivity problems, in: LATIN, 2008, pp. 423–435; Algorithmica, in press Kortsarz, 2003, Approximating node-connectivity problems via set covers, Algorithmica, 37, 75, 10.1007/s00453-003-1027-4 Kortsarz, 2007, Approximating minimum cost connectivity problems Nutov, 2006, Approximating minimum power covers of intersecting families and directed connectivity problems, vol. 4110, 236 Z. Nutov, Approximating minimum power k-connectivity, in: ADHOC-NOW, 2008, pp. 86–93 Z. Nutov, Approximating Steiner networks with node weights, in: LATIN, 2008, pp. 411–422 Z. Nutov, An almost O(logk)-approximation for k-connected subgraphs, in: SODA, 2009, pp. 912–921