English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

On embeddings in cycles

MPS-Authors

Hromkovic,  Juraj
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Müller,  Vladimír
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Sýkora,  Ondrej
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Vrto,  Imrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

91-122.pdf
(Any fulltext), 27MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Hromkovic, J., Müller, V., Sýkora, O., & Vrto, I.(1991). On embeddings in cycles (MPI-I-91-122). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B056-8
Abstract
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.