Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-91-122

On embeddings in cycles

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

MPI-I-91-122. November 1991, 22 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
91-122.pdf91-122.pdf26716 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-122
Hide details for BibTeXBibTeX
@TECHREPORT{HromkovicMuellerSykoraVrto91,
  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},
}