Grid spanners with low forwarding index for energy efficient networks

Frédéric Giroire 1 Stéphane Pérennes 1 Issam Tahiri 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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 [14], [1], [7], [5]. 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.
Liste complète des métadonnées

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01095179
Contributor : Frédéric Giroire <>
Submitted on : Monday, December 15, 2014 - 11:21:37 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Saturday, April 15, 2017 - 8:42:04 AM

File

report.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01095179, version 1

Collections

Citation

Frédéric Giroire, Stéphane Pérennes, Issam Tahiri. Grid spanners with low forwarding index for energy efficient networks. [Research Report] RR-8643, INRIA Sophia Antipolis; INRIA. 2014. 〈hal-01095179〉

Share

Metrics

Record views

493

Files downloads

135