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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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}


Linking options:
  • http://mi.mathnet.ru/eng/pdm696
  • http://mi.mathnet.ru/eng/pdm/y2020/i1/p87

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020