RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

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

Applied Graph Theory

A computation of the shortest paths in optimal two-dimensional circulant networks

E. A. Monakhova

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk, Russia

Abstract: A family of tight optimal two-dimensional 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 {2N-1}-1)/2$. For this family, two new improved versions of a shortest-path 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+1-2k\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)\rfloor-x+1$. The routing algorithms and their estimates are considered for using in topologies of networks-on-chip. For implementation in networks-on-chip 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{(N-1)/2} \rceil-1$.

Keywords: two-dimensional circulant networks, diameter, shortest paths, optimal generalized Petersen graphs, networks-on-chip.

 Funding Agency Grant Number Russian Academy of Sciences - Federal Agency for Scientific Organizations 0315-2016-0006

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 two-dimensional 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 two-dimensional circulant networks \jour Prikl. Diskr. Mat. \yr 2020 \issue 47 \pages 87--100 \mathnet{http://mi.mathnet.ru/pdm696} \crossref{https://doi.org/10.17223/20710410/47/7}