On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing
Recent developments in commutative algebra, linear algebra, and graph theory allow us to approach various issues in several fields. Circulant graphs now have a wider range of practical uses, including as the foundation for optical networks, discrete cellular neural networks, small-world networks, mo...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-12-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/1/10 |
| _version_ | 1797447104259424256 |
|---|---|
| author | Ahmed El-Mesady Aleksandr Y. Romanov Aleksandr A. Amerikanov Alexander D. Ivannikov |
| author_facet | Ahmed El-Mesady Aleksandr Y. Romanov Aleksandr A. Amerikanov Alexander D. Ivannikov |
| author_sort | Ahmed El-Mesady |
| collection | DOAJ |
| description | Recent developments in commutative algebra, linear algebra, and graph theory allow us to approach various issues in several fields. Circulant graphs now have a wider range of practical uses, including as the foundation for optical networks, discrete cellular neural networks, small-world networks, models of chemical reactions, supercomputing and multiprocessor systems. Herein, we are concerned with the decompositions of the bipartite circulant graphs. We propose the Cartesian and tensor product approaches as helping tools for the decompositions. The proposed approaches enable us to decompose the bipartite circulant graphs into many categories of graphs. We consider the use cases of applying the described theory of bipartite circulant graph decomposition to the problems of finding new topologies and deadlock-free routing in them when building supercomputers and networks-on-chip. |
| first_indexed | 2024-03-09T13:50:01Z |
| format | Article |
| id | doaj.art-4ce26c3d9d5d4a0288d25fc4267b45cf |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T13:50:01Z |
| publishDate | 2022-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-4ce26c3d9d5d4a0288d25fc4267b45cf2023-11-30T20:51:09ZengMDPI AGAlgorithms1999-48932022-12-011611010.3390/a16010010On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free RoutingAhmed El-Mesady0Aleksandr Y. Romanov1Aleksandr A. Amerikanov2Alexander D. Ivannikov3Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf 32952, EgyptHSE University, Moscow 101000, RussiaHSE University, Moscow 101000, RussiaInstitute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow 124365, RussiaRecent developments in commutative algebra, linear algebra, and graph theory allow us to approach various issues in several fields. Circulant graphs now have a wider range of practical uses, including as the foundation for optical networks, discrete cellular neural networks, small-world networks, models of chemical reactions, supercomputing and multiprocessor systems. Herein, we are concerned with the decompositions of the bipartite circulant graphs. We propose the Cartesian and tensor product approaches as helping tools for the decompositions. The proposed approaches enable us to decompose the bipartite circulant graphs into many categories of graphs. We consider the use cases of applying the described theory of bipartite circulant graph decomposition to the problems of finding new topologies and deadlock-free routing in them when building supercomputers and networks-on-chip.https://www.mdpi.com/1999-4893/16/1/10Cartesian productcirculant graphgraph decompositionnetwork-on-chiproutingsupercomputing |
| spellingShingle | Ahmed El-Mesady Aleksandr Y. Romanov Aleksandr A. Amerikanov Alexander D. Ivannikov On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing Algorithms Cartesian product circulant graph graph decomposition network-on-chip routing supercomputing |
| title | On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing |
| title_full | On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing |
| title_fullStr | On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing |
| title_full_unstemmed | On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing |
| title_short | On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing |
| title_sort | on bipartite circulant graph decompositions based on cartesian and tensor products with novel topologies and deadlock free routing |
| topic | Cartesian product circulant graph graph decomposition network-on-chip routing supercomputing |
| url | https://www.mdpi.com/1999-4893/16/1/10 |
| work_keys_str_mv | AT ahmedelmesady onbipartitecirculantgraphdecompositionsbasedoncartesianandtensorproductswithnoveltopologiesanddeadlockfreerouting AT aleksandryromanov onbipartitecirculantgraphdecompositionsbasedoncartesianandtensorproductswithnoveltopologiesanddeadlockfreerouting AT aleksandraamerikanov onbipartitecirculantgraphdecompositionsbasedoncartesianandtensorproductswithnoveltopologiesanddeadlockfreerouting AT alexanderdivannikov onbipartitecirculantgraphdecompositionsbasedoncartesianandtensorproductswithnoveltopologiesanddeadlockfreerouting |