Skip to Main content Skip to Navigation
New interface
Journal articles

Grid spanners with low forwarding index for energy efficient networks

Frédéric Giroire 1 Stéphane Pérennes 1 Issam Tahiri 2 
2 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
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Frédéric Giroire Connect in order to contact the contributor
Submitted on : Tuesday, November 14, 2017 - 10:19:50 AM
Last modification on : Thursday, August 4, 2022 - 4:58:28 PM
Long-term archiving on: : Thursday, February 15, 2018 - 12:54:40 PM


Files produced by the author(s)




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



Record views


Files downloads