Grid spanners with low forwarding index for energy efficient networks

详细信息    查看全文

• 作者：Frederic Giroire^a ; ^{frederic.giroire@cnrs.fr" class="auth_mail" title="E-mail the corresponding author} ; Stephane Perennes^a ; Issam Tahiri^b
• 关键词：spanning subgraphs ; forwarding index ; energy saving ; routing ; grid
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：52
• 期：Complete
• 页码：141-148
• 全文大小：265 K

文摘

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)$\pi (G,R)$ of G is the maximum number of paths in R passing through any edge of G. The forwarding index  π(G)$\pi (G)$ of G   is the minimum π(G,R)$\pi (G,R)$ over all routings R's of G. This parameter has been studied for different graph classes [Xu, J.-M. and M. Xu, The forwarding indices of graphs – a survey, CoRR abs/1204.2604 (2012)], [Bouabdallah, A. and D. Sotteau, On the edge forwarding index problem for small graphs, Networks23 (1993), pp. 249–255], [Fernandez de la Vega, W. and L. M. Gordones, The forwarding indices of random graphs, Random Structures and Algorithms 3 (1992), pp. 107–116], [de la Vega, W. F. and Y. Manoussakis, The forwarding index of communication networks with given connectivity, Discrete Appl. Math. 37–38 (1992), pp. 147–155]. 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.