Geodesic
Effective algorithm for finding shortest paths in~dense~Gaussian networks
Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 94-104.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: Dense Gaussian Networks, circulant graphs, shortest paths, networks on a chip. 
@article{PDM_2022_4_a8,
     author = {E. A. Monakhova and O. G. Monakhov},
     title = {Effective algorithm for finding shortest paths {in~dense~Gaussian} networks},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {94--104},
     publisher = {mathdoc},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_4_a8/}
}
TY  - JOUR
AU  - E. A. Monakhova
AU  - O. G. Monakhov
TI  - Effective algorithm for finding shortest paths in~dense~Gaussian networks
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 94
EP  - 104
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_4_a8/
LA  - ru
ID  - PDM_2022_4_a8
ER  - 
%0 Journal Article
%A E. A. Monakhova
%A O. G. Monakhov
%T Effective algorithm for finding shortest paths in~dense~Gaussian networks
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 94-104
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_4_a8/
%G ru
%F PDM_2022_4_a8
E. A. Monakhova; O. G. Monakhov. Effective algorithm for finding shortest paths in~dense~Gaussian networks. Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 94-104. http://geodesic.mathdoc.fr/item/PDM_2022_4_a8/

[1] Martinez C., Vallejo E., Beivide R., et al., “Dense Gaussian networks: Suitable topologies for on-chip multiprocessors”, Intern. J. Parallel Programming, 34 (2006), 193–211 | DOI

[2] Martinez C., Vallejo E., Moreto M., et al., “Hierarchical topologies for large-scale two-level networks”, XVI Jornadas de Paralelismo (Granada, Spain, September, 2005) https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.7372

[3] Martinez C., Beivide R., Stafford E., et al., “Modeling toroidal networks with the Gaussian integers”, IEEE Trans. Computers, 57:8 (2008), 1046–1056 | DOI | MR

[4] Flahive M. and Bose B., “The topology of Gaussian and Eisenstein — Jacobi interconnection networks”, IEEE Trans. Parall. Distrib. Syst., 21:8 (2010), 1132–1142 | DOI

[5] Pay K.-J., Yang J.-S., Chen G.-Y., and Chang J.-M., “Configuring protection routing via completely independent spanning trees in Dense Gaussian On-Chip Networks”, IEEE Trans. Netw. Sci. Eng., 9:2 (2022), 932–946 | DOI | MR

[6] Touzene A., “On all-to-all broadcast in dense Gaussian network on-chip”, IEEE Trans. Parall. Distrib. Syst., 26:4 (2015), 1085–1095 | DOI

[7] Alsaleh O., Bose B., and Hamdaoui B., “On-to-many node-disjoint paths routing in dense Gaussian networks”, Computer J., 58:2 (2015), 173–187 | DOI

[8] Bermond J.-C., Comellas F., and Hsu D. F., “Distributed loop computer networks: a survey”, J. Parallel Distrib. Comput., 24:1 (1995), 2–10 | DOI

[9] Hwang F. K., “A survey on multi-loop networks”, Theor. Comput. Sci., 299 (2003), 107–121 | DOI | MR

[10] Monakhova E. A., “Structural and communicative properties of circulant networks”, Prikladnaya Diskretnaya Matematika, 2011, no. 3(13), 92–115 (in Russian)

[11] Monakhova E. A., Romanov A. Y., and Lezhnev E. V., “Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for Networks-on-Chip”, IEEE Access, 8 (2020), 215010–215019 | DOI | MR

[12] Zerovnik J. and Pisanski T., “Computing the diameter in multiple-loop networks”, J. Algorithms, 14 (1993), 226–243 | DOI | MR

[13] Gomez D., Gutierrez J., Ibeas A., et al., “On finding a shortest path in circulant graphs with two jumps”, LNCS, 3595, 2005, 777–786 | MR

[14] Cai J. Y., Havas G., Mans B., et al., “On routing in circulant graphs”, LNCS, 1627, 1999, 360–369 | MR

[15] Monakhova E. A., Monakhov O. G., and Romanov A. Yu., “Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for Networks-on-Chip”, IEEE Trans. Network Science and Engineering, 2022 https://ieeexplore.ieee.org/document/9910381

[16] Monakhova E. and Monakhov O., “A generalized routing algorithm for a family of optimal 2D circulant networks based on relative addressing”, Proc. 17th Inter. Asian School-Seminar, OPCS-21 (Novosibirsk, Russia), 2021, 55–59 | MR

[17] Jha P. K., “Dimension-order routing algorithms for a family of minimal-diameter circulants”, J. Inter. Networks, 14:1 (2013), 1350002, 24 pp.

[18] Monakhova E. A., “Search for the shortest paths in optimal two-dimensional circulants”, Prikladnaya Diskretnaya Matematika, 2020, no. 47, 87–100 (in Russian) | MR

[19] Romanov A. Y., “Development of routing algorithms in networks-on-chip based on ring circulant topologies”, Heliyon, 5:4 (2019), e01516 | DOI

[20] Romanov A. Y., Lezhnev E. V., Glukhikh A. Y., and Amerikanov A. A., “Development of routing algorithms in networks-on-chip based on two-dimensional optimal circulant topologies”, Heliyon. Jan., 6:1 (2020), e03183 | DOI

[21] Camarero C., Martinez C., and Beivide R., “L-networks: A topological model for regular two-dimensional interconnection networks”, IEEE Trans. Computers, 62:7 (2013), 1362–1375 | DOI | MR

[22] Dijkstra E. W., “A note on two problems in connexion with graphs”, Numer. Math., 1:1 (1959), 269–271 | DOI | MR