Articles


Document Type
Journal article (JA)
Title
The optimal routing of augmented cubes
Author
Chen, Meirun(1); Naserasr, Reza(2)
Address
(1) School of Applied Mathematics, Xiamen University of Technology, Xiamen; Fujian; 361024, China; (2) CNRS, IRIF, UMR 8243, Université Paris Diderot – Paris 7, France
RPAddress
Email
ResearchID
ORCID
Journal
Information Processing Letters
Publisher
Elsevier B.V.
ISSN
0020-0190
Published
2018-08, 136:59-63.
JCR
ImpactFactor
ISBN
Fund_Code
HYMC
HYDD
HYKSRQ
HYJSRQ
HYLWLB
HYJB
Keywords
Geometry - Interconnection networks (circuit switching) - Network routing
Abstract
A routing in a graph G is a set of paths connecting each ordered pair of vertices. Load of an edge e is the number of times it appears on these paths. The edge-forwarding index of G is the smallest of maximum loads over all routings. Augmented cube of dimension n, AQn, is the Cayley graph (Z2n,{e1,e2,…,en,J2,…,Jn}) where ei's are the vectors of the standard basis and Ji=∑j=n?i+1nej. S.A. Choudum and V. Sunitha showed that the greedy algorithm provides a shortest path between each pair of vertices of AQn. Min Xu and Jun-Ming Xu claimed that this routing also proves that the edge-forwarding index of AQnis 2n?1. Here we disprove this claim, by showing that in this specific routing some edges are repeated nearly [Formula presented]2n?1times (to be precise, ?[Formula presented]? for even values of n and ?[Formula presented]? for odd values of n). However, by providing other routings, we prove that 2n?1is indeed the edge-forwarding index of AQn. ? 2018 Elsevier B.V.
WOS Categories
Accession Number
EI收录号
20181705038153
DOI
10.1016/j.ipl.2018.04.003
ESI_Type
COMPUTER
Collection
EI

Back to List