next up previous contents
Next: Chordal Rings Up: Specific Class of Graphs Previous: Extremal Compactness   Contents


Interconnection Networks

We list in this paragraph the results about the graphs used for multi-processor based architectures.


\begin{theorem}[\cite{SK85}]\mbox{}
\beginsmall{itemize}
\item $\mbox{\rm SIRS}(...
...
\item $\mbox{\rm SIRS}(\mbox{\em rings}) = 1$.
\endsmall{itemize}
\end{theorem}


\begin{theorem}[\cite{vLT87}]
\mbox{}
\beginsmall{itemize}
\item $\mbox{\rm SLIR...
...S}(\mbox{\em complete bipartite graphs}) = 1$.
\endsmall{itemize}
\end{theorem}

A more accurate form of the last point is presented in theorems 39, and 40 in Section 3.7.


\begin{theorem}[\cite{BLT91}]\mbox{}
\beginsmall{itemize}
\item $\mbox{\rm SLIRS...
...$, if each dimension
is of length at most~$4$.
\endsmall{itemize}
\end{theorem}

Applying the results of the product of graphs [KKR93,FG98] it is quite easy to show:


\begin{theorem}[\cite{KKR93,FG98a}]\mbox{}
\beginsmall{itemize}
\item $\mbox{\rm...
...x{\rm SLIRS}(d\mbox{\em -dimensional tori})=2$.
\endsmall{itemize}
\end{theorem}


\begin{theorem}[\cite{KRS97}]
\mbox{}
\beginsmall{itemize}
\item $\mbox{\rm IRS}...
...ar graph}) = \Omega(n(\log\log{n}/\log{n})^5)$.
\endsmall{itemize}
\end{theorem}

Open question 5    
- Are the bounds of Theorem 23 tight?

There are some experimental results in [SML94] about the stretch factor and the average stretch factor of 2D-grids and Tori with different general labeling algorithms.


\begin{theorem}[\cite{SML94}]
For every $d \geqs 4$, $1$-$\mbox{\rm stretch}(d\mbox{\em -dimensional tori}) \leqs
(d-2)/2$.
\end{theorem}




2000-03-21