MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


On embeddings in cycles

Hromkovic, Juraj and Müller, Vladimír and Sýkora, Ondrej and Vrto, Imrich

November 1991, 22 pages.

Status: available - back from printing

We prove several exact results for the dilation of well-known interconnection networks in cycles, namely : ${\rm dil}(T_{t,r},C_{(t^{r-1}-1)/(r-1)})=\lceil t(t^{r-1}-1)/(2(r-1)(t-1))\rceil,$ for complete $r$-level $t$-ary trees, ${\rm dil}(Q_n,C_{2^n}) =\sum_{k=0}^{n-1}{k\choose \lfloor \frac{k}{2}\rfloor },$ for $n$-dimensional hypercubes, ${\rm dil}(P_n\times P_n\times P_n,C_{n^3})= \lfloor 3n^2/4+n/2\rfloor,$ for 3-dimensional meshes (where $P_n$ is an $n$-vertex path) and ${\rm dil}(P_m\times P_n,C_{mn})= {\rm dil}(C_m\times P_n,C_{mn})={\rm dil}(C_m\times C_n,C_{mn})=\min\{m,n\},$ for 2-dimensional ordinary, cylindrical and toroidal meshes, respectively. The last results solve three remaining open problems of the type $"{\rm dil}(X\times Y, Z)=?"$, where $X,\ Y$ and $Z$ are paths or cycles. The previously known dilations are: ${\rm dil}(P_m\times P_n,P_{mn})= \min \{m,n\}$, ${\rm dil}(C_m\times P_n,P_{mn})=\min \{m,2n\}$ and ${\rm dil}(C_m\times C_n,P_{mn}) =2\min \{m,n\}$, if $m\neq n$, otherwise ${\rm dil}(C_n\times C_n)=2n-1$ . The proofs of the above stated results are based on the following technique. We find a suficient condition for a graph $G$ which assures the equality ${\rm dil}(G,C_n)={\rm dil}(G,P_n)$. We prove that trees, X-trees, meshes, hypercubes, pyramides and tree of meshes satisfy the condition. Using known optimal dilations of complete trees, hypercubes and 2- and 3-dimensional meshes in path we get the above exact result.

  • 91-122.pdf91-122.pdf
  • Attachement: 91-122.pdf (26716 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Hromkovic, Juraj and M{\"u}ller, Vladim{\'i}r and Sýkora, Ondrej and Vrto, Imrich},
  TITLE = {On embeddings in cycles},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-122},
  MONTH = {November},
  YEAR = {1991},
  ISSN = {0946-011X},