Min-Max Coverage in Multi-interface Networks

Abstract : We consider devices equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of establishing the connections defined by a network G = (V,E) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes V represent the devices, edges E represent the connections that must be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges. We prove that the problem is NP-hard for any fixed Δ ≥ 5 and k ≥ 16, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that the problem cannot be approximated within Ω(ln Δ). We then provide a general approximation algorithm which guarantees a factor of O((1 + b)ln (Δ)), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented.
Type de document :
Communication dans un congrès
Ivana Cerná and Tibor Gyimóthy and Juraj Hromkovic and Keith Jefferey and Rastislav Královic and Marko Vukolic and Stefan Wolf. 37th Conference on Current Trends in Theory and Practice of Computer Science, Jan 2011, Nový Smokovec, Slovakia. Springer, 6543, pp.190-201, 2011, Lecture Notes in Computer Science; SOFSEM 2011: Theory and Practice of Computer Science. <10.1007/978-3-642-18381-2_16>
Liste complète des métadonnées

https://hal.inria.fr/hal-00644084
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 15:18:42
Dernière modification le : mardi 22 mai 2012 - 16:24:40
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:29:46

Fichier

MultiInterfacesCoverage.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra. Min-Max Coverage in Multi-interface Networks. Ivana Cerná and Tibor Gyimóthy and Juraj Hromkovic and Keith Jefferey and Rastislav Královic and Marko Vukolic and Stefan Wolf. 37th Conference on Current Trends in Theory and Practice of Computer Science, Jan 2011, Nový Smokovec, Slovakia. Springer, 6543, pp.190-201, 2011, Lecture Notes in Computer Science; SOFSEM 2011: Theory and Practice of Computer Science. <10.1007/978-3-642-18381-2_16>. <hal-00644084>

Partager

Métriques

Consultations de
la notice

254

Téléchargements du document

85