Relay Placement for Two-Connectivity

Abstract : 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.
Type de document :
Communication dans un congrès
Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.366-377, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_29〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01531964
Contributeur : Hal Ifip <>
Soumis le : vendredi 2 juin 2017 - 11:23:22
Dernière modification le : vendredi 2 juin 2017 - 11:25:01
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 09:04:23

Fichier

978-3-642-30054-7_29_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Gruia Calinescu. Relay Placement for Two-Connectivity. Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.366-377, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_29〉. 〈hal-01531964〉

Partager

Métriques

Consultations de la notice

35

Téléchargements de fichiers

13