Grid spanners with low forwarding index for energy efficient networks

Frédéric Giroire 1 Stéphane Pérennes 2 Issam Tahiri 3
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : A routing R of a connected graph G is a collection that contains simple paths connecting every ordered pair of vertices in G. The edge-forwarding index with respect to R (or simply the forwarding index with respect to $R) π(G, R)$ of G is the maximum number of paths in R passing through any edge of G. The forwarding index $π(G)$ of G is the minimum $π(G, R)$ over all routings R's of G. This parameter has been studied for different graph classes (1), (2), (3), (4). Motivated by energy efficiency, we look, for different numbers of edges, at the best spanning graphs of a square grid, namely those with a low forwarding index.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2017, 〈10.1016/j.dam.2017.02.021〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01634448
Contributeur : Frédéric Giroire <>
Soumis le : mardi 14 novembre 2017 - 10:19:50
Dernière modification le : mercredi 15 novembre 2017 - 01:15:47

Fichier

journal-dam.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frédéric Giroire, Stéphane Pérennes, Issam Tahiri. Grid spanners with low forwarding index for energy efficient networks. Discrete Applied Mathematics, Elsevier, 2017, 〈10.1016/j.dam.2017.02.021〉. 〈hal-01634448〉

Partager

Métriques

Consultations de la notice

17

Téléchargements de fichiers

4