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

00200190

Published

201808, 136:5963.

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 edgeforwarding 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 JunMing Xu claimed that this routing also proves that the edgeforwarding 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 edgeforwarding 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