HYPER-RING CONNECTION MACHINES

A graph G = (V, E) is called a hyper-ring with N nodes (N-HR for short ) if V = {0,..., N - 1} and E = {{u, v} / v - u module N is a power of 2). We study constructions, properties, spanners of HRs, and embeddin gs into HRs. A hypercube with N nodes, a grid of size a x b, and a com plete 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(2) N], 2k - 1 for any 1 less than or equal to k less than or equal to [log(2) N], and 2k - 1 for any 2 less than or equal to K less than or equal to [log(2) N] -1, respectively. The numbers of edges of these types of spanners are N - 1, at most N[(log2 N) /k], a nd at most N([log(2) N] - k)/(2k) + Nk, respectively. Some of these sp anners are superior in both stretch factors and numbers of edges to co rresponding spanners for synchronizer gamma of HRs.