๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A d-move local permutation routing for the d-cube

โœ Scribed by Frank K. Hwang; Y.C. Yao; Miltos D. Grammatikakis

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
680 KB
Volume
72
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Optimal packet routing algorithms for all binary d-cubes of dimension d < 7 are presented. The algorithms given are synchronous, offer distributed control, and assume d-port, multiacccpting communication.

While the previous best known packet routing algorithm [3] on the 7-cube takes 11 time-units, our algorithm has reduced the worst-case time complexity to the minimum possible of 7 units. We also give an optimal routing algorithm for the ternary 4-cube.

๐Ÿ“œ SIMILAR VOLUMES

A Lower Bound for the Simplexity of then
A Lower Bound for the Simplexity of then-Cube via Hyperbolic Volumes
โœ Warren D. Smith ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 139 KB

Let T (n) denote the number of n-simplices in a minimum cardinality decomposition of the n-cube into n-simplices. For n โ‰ฅ 1, we show that T (n) โ‰ฅ H (n), where H (n) is the ratio of the hyperbolic volume of the ideal cube to the ideal regular simplex. Explicit bounds for T (n) are tabulated for n โ‰ค