Recent zbMATH articles in MSC 68W35 https://www.zbmath.org/atom/cc/68W35 2021-03-30T15:24:00+00:00 Werkzeug A computation of the shortest paths in optimal two-dimensional circulant networks. https://www.zbmath.org/1455.68146 2021-03-30T15:24:00+00:00 "Monakhova, E. A." https://www.zbmath.org/authors/?q=ai:monakhova.eh-a Summary: 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_2N \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$$.