Effective algorithm for finding shortest paths in~dense~Gaussian networks

E. A. Monakhova ; O. G. Monakhov

Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 94-104

Résumé

As a promising topology of networks on a chip, we consider a family of Dense Gaussian Networks, which are optimal circulant degree four graphs of the form $C(D^2+(D+1)^2; D, D+1)$. For this family, an algorithm for finding the shortest paths between graph vertices is proposed, which uses relative addressing of vertices and, unlike a number of the known algorithms, allows to calculate the shortest paths without using the coordinates of neighboring lattice zeros in a dense tessellation of graphs on the $\mathbb{Z}^2$ plane. This reduces the memory and execution time costs compared to other algorithms when the new algorithm is implemented on a network-on-chip with a Dense Gaussian Network topology.

Détail

Keywords: Dense Gaussian Networks, circulant graphs, shortest paths, networks on a chip.