%0 Conference Proceedings
%T Relay Placement for Two-Connectivity
%+ Illinois Institute of Technology (IIT)
%A Calinescu, Gruia
%Z Part 8: Wireless Networks II
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 11th International Networking Conference (NETWORKING)
%C Prague, Czech Republic
%Y Robert Bestak
%Y Lukas Kencl
%Y Li Erran Li
%Y Joerg Widmer
%Y Hao Yin
%I Springer
%3 NETWORKING 2012
%V LNCS-7290
%N Part II
%P 366-377
%8 2012-05-21
%D 2012
%R 10.1007/978-3-642-30054-7_29
%K wireless and sensor networks
%K approximation algorithms
%K Steiner nodes
%Z Computer Science [cs]
%Z Computer Science [cs]/Networking and Internet Architecture [cs.NI]Conference papers
%X Motivated by applications to wireless sensor networks, we study the following problem. We are given a set S of wireless sensor nodes, given as a multiset of points in a normed space. We must place a minimum-size (multi)set Q of wireless relay nodes in the normed space such that the unit-disk graph induced by Q ∪ S is two-connected. The unit-disk graph of a set of points has an edge between two points if their distance is at most 1.Kashyap, Khuller, and Shayman (Infocom 2006) present algorithms for the two variants of the problem: two-edge-connectivity and biconnectivity. For both they prove an approximation ratio of at most 2 dMST, where dMST is the maximum degree of a minimum-degree Minimum Spanning Tree in the normed space. In the Euclidean two and three dimensional spaces, dMST = 5, and dMST = 13 respectively. We give a tight analysis of the same algorithms, obtaining approximation ratios of dMST for biconnectivity and 2 dMST − 1 for two-edge-connectivity respectively.
%G English
%Z TC 6
%2 https://inria.hal.science/hal-01531964/document
%2 https://inria.hal.science/hal-01531964/file/978-3-642-30054-7_29_Chapter.pdf
%L hal-01531964
%U https://inria.hal.science/hal-01531964
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC6
%~ IFIP-LNCS-7290
%~ IFIP-NETWORKING