EMBEDDING TORUS ON THE STAR GRAPH

Authors
SAIKIA DK BADRINATH R SEN RK
Citation
Dk. Saikia et al., EMBEDDING TORUS ON THE STAR GRAPH, IEEE transactions on parallel and distributed systems, 9(7), 1998, pp. 650-663
Citations number
12
Categorie Soggetti
Computer Science Theory & Methods","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
9
Issue
7
Year of publication
1998
Pages
650 - 663
Database
ISI
SICI code
1045-9219(1998)9:7<650:ETOTSG>2.0.ZU;2-2
Abstract
In this paper, we present a scheme for efficient embedding of torus of any dimension on a star graph. The dilation of the embedding is four. The expansion is small. Congestion depends upon the routing scheme us ed. With one routing scheme, the congestion is bound by a small consta nt (approximate to 2) with an increase in expansion cost. For a second routing scheme, the congestion is O(n), for an n-star, with bounded e xpansion.