Article ID Journal Published Year Pages File Type
429227 Information Processing Letters 2007 5 Pages PDF
Abstract

For a given connected graph G of order n, a routing R in G is a set of n(nāˆ’1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2002) 71–84] proposed a variant of the hypercube Qn, called the augmented cube AQn and presented a minimal routing algorithm. This paper determines the vertex and the edge forwarding indices of AQn as and 2nāˆ’1, respectively, which shows that the above algorithm is optimal in view of maximizing the network capacity.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics