Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429227 | Information Processing Letters | 2007 | 5 Pages |
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