Recent zbMATH articles in MSC 68W35https://www.zbmath.org/atom/cc/68W352021-03-30T15:24:00+00:00WerkzeugA computation of the shortest paths in optimal two-dimensional circulant networks.https://www.zbmath.org/1455.681462021-03-30T15:24:00+00:00"Monakhova, E. A."https://www.zbmath.org/authors/?q=ai:monakhova.eh-aSummary: 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\).