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 modulo N is a power of 2}. We study constructions and spanners of HRs, and embeddings into HRs. The stretch factors of three types of spanners given in this paper are at most [log₂ N], 2k-1 for any 1⩽k⩽[log₂ N], and 2k-1 for any 0⩽k⩽[log₂ N]-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 γ of HRs