×

Power assignment for \(k\)-connectivity in wireless ad hoc networks. (English) Zbl 1079.90512

Summary: The problem min-power \(k\)-connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is \(k\)-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a \(3k\)-approximation algorithm for any \(k \geq 3\), a \((k+12H(k))\)-approximation algorithm for \(k(2k-1) \leq n\) where \(n\) is the network size, a \((k +2 \lceil (k +1)/2\rceil)\)-approximation algorithm for \(2 \leq k \leq 7\), a 6-approximation algorithm for \(k=3\), and a 9-approximation algorithm for \(k=4\).

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. Auletta, Y. Dinitz, Z. Nutov, and D. Parente, ”A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph,” J. Algorithms, vol. 31, pp. 21–30, 1999. · Zbl 0951.68111 · doi:10.1006/jagm.1999.1006
[2] D.M. Blough, M. Leoncini, G. Resta, and P. Santi, ”On the symmetric range assignment problem in wireless ad hoc networks,” in Proc. 2nd IFIP International Conference on Theoretical Computer Science, Montreal, August 2002.
[3] G. Calinescu, I. Mandoiu, and A. Zelikovsky, ”Symmetric connectivity with minimum power consumption in radio networks submitted for journal publication, preliminary results appeared,” in Proc. 2nd IFIP International Conference on Theoretical Computer Science, 2002, pp. 119–130.
[4] G. Calinescu and P.-J. Wan, High Connectivity with Minimum Total Power in Wireless Ad Hoc Netowrks, Ad Hoc Now, 2003.
[5] J. Cheriyan and S.N. Maheshwari, ”Finding nonseparating induced cycles and independent spanning trees in connected graphs,” J. Algorithms, vol. 9, pp. 507–537, 1988. · Zbl 0672.05056 · doi:10.1016/0196-6774(88)90015-6
[6] J.Cheriyan, S. Vempala, and A.Vetta, ”Approximation algorithms for minimum-cost \(k\)-vertex connected subgraphs,” in Proc. 34th Ann. ACM STOC, May 2002, pp. 306–312. · Zbl 1192.68883
[7] Y. Dinitz and Z. Nutov, ”A 3-approximation algorithm for finding optimum 4/5-vertex-connected spanning subgraphs,” Journal of Algorithms, vol. 32, pp. 31–40, 1999. · Zbl 0951.68112 · doi:10.1006/jagm.1999.1007
[8] A. Frank and É. Tardos, ”An application of submodular flows,” Linear Algebra and its Applications, vols. 114/115, pp. 329–348, 1989. · Zbl 0672.05035 · doi:10.1016/0024-3795(89)90469-2
[9] H.N. Gabow, ”A representation for crossing set families with applications to submodular flow problems,” in Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, 1993, pp. 202–211. · Zbl 0801.68084
[10] M.T. Hajiaghayi, N. Immorlica, and V.S. Mirrokni, ”Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks,” in Proceedings of the 9th annual international conference on Mobile computing and networking, 2003, pp. 300–312.
[11] G.Kortsarz and Z. Nutov, ”Approximating node connectivity problems via set covers,” in Third International Workshop on Approximation Algorithms for Combinatorial Optimization, (APPROX 2000), Springer, LNCS, vol. 1913, 2000, pp. 194–205. · Zbl 0976.05061
[12] W. Mader, ”Ecken vom Grad \(n\) ”in minimalen \(n\)-fach zusammenhängenden Graphen,” Arch. Math, vol. 23, pp. 219–224, 1972. · Zbl 0233.05119 · doi:10.1007/BF01304873
[13] W. Mader ”Degree and local connectivity in finite graphs,” Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974, Academia, Prague 1975), pp. 341–344.
[14] W. Mader, ”On \(k\)-con-critically \(n\)-connected Graphs,” Journal of Combinatorial Theory, Series B, vol. 86, pp. 296–314, 2002. · Zbl 1024.05052 · doi:10.1006/jctb.2002.2129
[15] A. Zehavi and A. Itai, ”Three tree-paths,” J. of Graph Theory, vol. 13, no. 2, pp. 177–188, 1989. · Zbl 0698.05049 · doi:10.1002/jgt.3190130205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.