Grid spanners with low forwarding index for energy efficient networks

Frédéric Giroire, Perennes, Stephane, Issam Tahiri

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.
BibTeX
@article{giroire2018grid,
  author = {Frédéric Giroire and Perennes, Stephane and Issam Tahiri},
  title = {{Grid spanners with low forwarding index for energy efficient networks}},
  journal = {Discret. Appl. Math.},
  year = {2018},
  doi = {10.1016/j.dam.2017.02.021},
}

Loading related content...

Figure