Minimize the Maximum Duty in Multi-interface Networks

Abstract : We consider devices equipped with multiple wired or wireless interfaces. By switching of various 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 two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage 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, unless P=NP, the problem cannot be approximated within a factor of ηln Δ, for a certain constant η. 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. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Δ≥3 and k≥10. Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of ηln Δ, for a certain constant η. We then provide approximation and exact algorithms for the general problem and for special cases, respectively.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2012, 63 (1-2), pp.274-295. <10.1007/s00453-011-9531-4>
Liste complète des métadonnées

https://hal.inria.fr/hal-00643961
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 13:02:37
Dernière modification le : jeudi 6 septembre 2012 - 18:48:43
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:25:07

Fichier

Min-Max-coverage.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra. Minimize the Maximum Duty in Multi-interface Networks. Algorithmica, Springer Verlag, 2012, 63 (1-2), pp.274-295. <10.1007/s00453-011-9531-4>. <hal-00643961>

Partager

Métriques

Consultations de
la notice

235

Téléchargements du document

152