
Prikl. Diskr. Mat., 2020, Number 47, Pages 87–100
(Mi pdm696)




Applied Graph Theory
A computation of the shortest paths in optimal twodimensional circulant networks
E. A. Monakhova^{} ^{} Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk, Russia
Abstract:
A family of tight optimal twodimensional circulant networks designed by analytical formulas has a description of the form $C(N;d,d+1)$, where $N$ is the order of a graph and the generator $d$ is the nearest integer to $(\sqrt {2N1}1)/2$. For this family, two new improved versions of a shortestpath routing algorithm with a complexity $O(1)$ are presented. Simple proofs for formulas used for routing algorithms based on the plane tessellation are received. In the routing algorithm, for a graph $C(N;d,d+1)$ the following formulas for the computing shortest routing vector $(x,y)$ from 0 to a node $k\le \lfloor N/2 \rfloor$ are used: if $k\bmod(d+1)=0$ or $\lfloor k/(d+1)\rfloor<d+12k\bmod(d+1)$, then $x=k\bmod(d+1)$, $y=\lfloor k/(d+1)\rfloor x$, else $x=k\bmod(d+1)+d+1$, $y= =\lfloor k/(d+1)\rfloorx+1$. The routing algorithms and their estimates are considered for using in topologies of networksonchip. For implementation in networksonchip the proposed routing algorithm requires $ \lceil \log_{2}N \rceil+ \lceil \log_{2}\lceil \sqrt{N/2} \rceil \rceil$ bits. New versions of the routing algorithm improve also the routing algorithm proposed early by the author for optimal generalized Petersen graphs with an analytical description of the form $P(N,a,a+1)$, where $2N$ is the order of a graph and $a = \lceil \sqrt{(N1)/2} \rceil1$.
Keywords:
twodimensional circulant networks, diameter, shortest paths, optimal generalized Petersen graphs, networksonchip.
DOI:
https://doi.org/10.17223/20710410/47/7
Full text:
PDF file (985 kB)
References:
PDF file
HTML file
UDC:
519.87
Citation:
E. A. Monakhova, “A computation of the shortest paths in optimal twodimensional circulant networks”, Prikl. Diskr. Mat., 2020, no. 47, 87–100
Citation in format AMSBIB
\Bibitem{Mon20}
\by E.~A.~Monakhova
\paper A computation of the shortest paths in optimal twodimensional circulant networks
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 47
\pages 87100
\mathnet{http://mi.mathnet.ru/pdm696}
\crossref{https://doi.org/10.17223/20710410/47/7}
Linking options:
http://mi.mathnet.ru/eng/pdm696 http://mi.mathnet.ru/eng/pdm/y2020/i1/p87
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  64  Full text:  10  References:  1 
