The forwarding indices of augmented cubes
- 作者：Min Xu ; Jun-Ming Xu
- 关键词：Combinatorial problems ; Augmented cubes ; Routings ; Forwarding index
- 刊名：Information Processing Letters
- 出版年：2007
- 期刊代码：61_00200190
- 类别：cp
- 出版时间：16 March 2007
- 卷：101
- 期：5
- 页码：185-189
- 文件大小：135 K
摘要
For a given connected graph G of order n, a routing R in G is a set of decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V0F-4M6SBP8-1&_mathId=mml1&_user=10&_cdi=5645&_rdoc=3&_acct=C000050221&_version=1&_userid=10&md5=f6c9b7c76a03d7636acc44ed43180e99" title="Click to view the MathML source">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 decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V0F-4M6SBP8-1&_mathId=mml2&_user=10&_cdi=5645&_rdoc=3&_acct=C000050221&_version=1&_userid=10&md5=7959e6e63066c0dad089efd9a04c1b8a" title="Click to view the MathML source">Qn, called the augmented cube decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V0F-4M6SBP8-1&_mathId=mml3&_user=10&_cdi=5645&_rdoc=3&_acct=C000050221&_version=1&_userid=10&md5=c10e5eb7ec8ed593176dbe420290e78c" title="Click to view the MathML source">AQn and presented a minimal routing algorithm. This paper determines the vertex and the edge forwarding indices of decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V0F-4M6SBP8-1&_mathId=mml4&_user=10&_cdi=5645&_rdoc=3&_acct=C000050221&_version=1&_userid=10&md5=25fa0927fc3f6d84e15ec1ec8d1f2790" title="Click to view the MathML source">AQn as and decoration:none; color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V0F-4M6SBP8-1&_mathId=mml6&_user=10&_cdi=5645&_rdoc=3&_acct=C000050221&_version=1&_userid=10&md5=5cc61618e92b36577b566d735f7eb28e" title="Click to view the MathML source">2n−1, respectively, which shows that the above algorithm is optimal in view of maximizing the network capacity.