https://hal.inria.fr/hal-01531964Calinescu, GruiaGruiaCalinescuIIT - Illinois Institute of TechnologyRelay Placement for Two-ConnectivityHAL CCSD2012wireless and sensor networksapproximation algorithmsSteiner nodes[INFO] Computer Science [cs][INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]Ifip, HalRobert BestakLukas KenclLi Erran LiJoerg WidmerHao Yin2017-06-02 11:23:222019-02-13 11:00:062017-06-02 11:25:01enConference papershttps://hal.inria.fr/hal-01531964/document10.1007/978-3-642-30054-7_29application/pdf1Motivated 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.