Grid spanners with low forwarding index for energy efficient networks

Frédéric Giroire 1 Stephane Perennes 1 Issam Tahiri 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 [12], [1], [5], [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 :
Communication dans un congrès
International Network Optimization Conference (INOC), May 2015, Warsaw, Poland. Electronic Notes in Discrete Mathematics
Liste complète des métadonnées


https://hal.inria.fr/hal-01218411
Contributeur : Frédéric Giroire <>
Soumis le : mercredi 21 octobre 2015 - 10:33:28
Dernière modification le : vendredi 23 octobre 2015 - 01:05:39
Document(s) archivé(s) le : vendredi 22 janvier 2016 - 21:35:00

Fichier

camera-ready-inoc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01218411, version 1

Collections

Citation

Frédéric Giroire, Stephane Perennes, Issam Tahiri. Grid spanners with low forwarding index for energy efficient networks . International Network Optimization Conference (INOC), May 2015, Warsaw, Poland. Electronic Notes in Discrete Mathematics. <hal-01218411>

Partager

Métriques

Consultations de
la notice

152

Téléchargements du document

52