Back to Search
Start Over
Routing Number Of A Pyramid
- Publication Year :
- 2016
-
Abstract
- In this short note we give the routing number of pyramid graph under the \textit{routing via matching} model introduced by Alon et al\cite{5}. This model can be viewed as a communication scheme on a distributed network. The nodes in the network can communicate via matchings (a step), where a node exchanges data with its partner. Formally, given a connected graph $G$ with vertices labeled from $[1,...,n]$ and a permutation $\pi$ giving the destination of pebbles on the vertices the problem is to find a minimum step routing scheme. This is denoted as the routing time $rt(G,\pi)$ of $G$ given $\pi$. We show that a $d$-dimensional pyramid with $m$ levels has a routing number of $O(dN^{1/d})$.<br />Comment: 3 pages, 2 figures
- Subjects :
- Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1611.07933
- Document Type :
- Working Paper