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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 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 (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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-01634448
Contributor : Frédéric Giroire <>
Submitted on : Tuesday, November 14, 2017 - 10:19:50 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Thursday, February 15, 2018 - 12:54:40 PM

File

journal-dam.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

332

Files downloads

43