Short communication Hyper-ring connection machines
Tom Altman, Yoshihide Igarashi, Koji Obokata · 1995
A graph G = (V, E) is called a hyper-ring with N nodes (N-HR for short) if I/= (0,. . . , N - l} and E = ({u, U} I u - u modulo N is a power of 2). We study constructions, properties, spanners of HRs, and embeddings into HRs. A hypercube with N nodes, a grid of size a x b, and a complete binary tree with N nodes can be embedded as subgraphs into an N-HR. The stretch factors of three types of spanners given in this paper are at most [log, N], 2k - 1 for any 1 I k I [log, Nl, and 2k - 1 for any 2 I k I [log, Nl- 1, respectively. The numbers of edges of these types of spanners are N - 1, at most N[(log, N)/k], and at most N([log, N] - k)/(2k) + Nk, respectively. Some of these spanners are superior in both stretch factors and numbers of edges to corresponding spanners for synchronizer y of HRs.