Embeddings of Hyper-Rings in Hypercubes

Yukihiro HAMADA  Aohan MEI  Yasuaki NISHITANI  Yoshihide IGARASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.11   pp.1606-1613
Publication Date: 1995/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
hyper-ring,  hypercube,  embedding,  dilation,  congestion,  

Full Text: PDF>>
Buy this Article

A graph G = (V, E) with N nodes is called an N-hyper-ring if V = {0, ..., N-1} and E = {(u, v)(u-v) modulo N is power of 2}. We study embeddings of the 2n-hyper-ring in the n-dimensional hypercube. We first show a greedy embedding with dilation 2 and congestion n+1. We next modify the greedy embedding, and then we obtain an embedding with dilation 4 and congestion 6.