{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T13:17:46Z","timestamp":1771075066195,"version":"3.50.1"},"reference-count":55,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T00:00:00Z","timestamp":1671667200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Basic Research Program at the National Research University Higher School of Economics (HSE University)"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a16010010","type":"journal-article","created":{"date-parts":[[2022,12,23]],"date-time":"2022-12-23T01:42:13Z","timestamp":1671759733000},"page":"10","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2009-3905","authenticated-orcid":false,"given":"Ahmed","family":"El-Mesady","sequence":"first","affiliation":[{"name":"Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf 32952, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9410-9431","authenticated-orcid":false,"given":"Aleksandr Y.","family":"Romanov","sequence":"additional","affiliation":[{"name":"HSE University, Moscow 101000, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5970-2125","authenticated-orcid":false,"given":"Aleksandr A.","family":"Amerikanov","sequence":"additional","affiliation":[{"name":"HSE University, Moscow 101000, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8162-5288","authenticated-orcid":false,"given":"Alexander D.","family":"Ivannikov","sequence":"additional","affiliation":[{"name":"Institute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow 124365, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1756-0381-4-10","article-title":"Using graph theory to analyze biological networks","volume":"4","author":"Pavlopoulos","year":"2011","journal-title":"BioData Min."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1038\/nrg2484","article-title":"RNA-Seq: A revolutionary tool for transcriptomics","volume":"10","author":"Wang","year":"2009","journal-title":"Nat. Rev. Genet."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"200","DOI":"10.5808\/GI.2013.11.4.200","article-title":"Review of Biological Network Data and Its Applications","volume":"11","author":"Yu","year":"2013","journal-title":"Genom. Inform."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1038\/340245a0","article-title":"A novel genetic system to detect protein\u2013protein interactions","volume":"340","author":"Fields","year":"1989","journal-title":"Nature"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1093\/embo-reports\/kve184","article-title":"A protein\u2013protein interaction map of the Caenorhabditis elegans 26S proteasome","volume":"2","author":"Davy","year":"2001","journal-title":"EMBO Rep."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"4569","DOI":"10.1073\/pnas.061034498","article-title":"A comprehensive two-hybrid analysis to explore the yeast protein interactome","volume":"98","author":"Ito","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"4879","DOI":"10.1073\/pnas.080078197","article-title":"Genome-wide analysis of vaccinia virus protein-protein interactions","volume":"97","author":"McCraith","year":"2000","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1038\/35051615","article-title":"The protein\u2013protein interaction map of Helicobacter pylori","volume":"409","author":"Rain","year":"2001","journal-title":"Nature"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/35001009","article-title":"A comprehensive analysis of protein\u2013protein interactions in Saccharomyces cerevisiae","volume":"403","author":"Uetz","year":"2000","journal-title":"Nature"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2309","DOI":"10.1021\/ja00842a001","article-title":"Theory of Chemical Reaction Networks. All Possible Mechanisms or Synthetic Pathways with Given of Reaction Steps or Species","volume":"97","year":"1975","journal-title":"J. Am. Chem. Soc."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1080\/09720529.2021.1885806","article-title":"On some applications related with algebraic structures through different well known graphs","volume":"24","author":"Nadeem","year":"2021","journal-title":"J. Discret. Math. Sci. Cryptogr."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1515\/math-2020-0003","article-title":"On applications of bipartite graph associated with algebraic structures","volume":"18","author":"Zhang","year":"2020","journal-title":"Open Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/j.physa.2006.04.047","article-title":"Bipartite graphs as models of complex networks","volume":"371","author":"Guillaume","year":"2006","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0166-218X(99)00143-2","article-title":"Counting symmetric configurations v3","volume":"99","author":"Betten","year":"2000","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"993","DOI":"10.15244\/pjoes\/75961","article-title":"Role of Graph Theory to Facilitate Landscape Connectivity: Subdivision of a Harary Graph","volume":"27","author":"Arif","year":"2018","journal-title":"Polish J. Environ. Stud."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1078","DOI":"10.1016\/j.ipl.2009.05.011","article-title":"Lucky labelings of graphs","volume":"109","author":"Grytczuk","year":"2009","journal-title":"Inf. Process. Lett."},{"key":"ref_17","unstructured":"Bonchev, D. (1991). Chemical Graph Theory: Introduction and Fundamentals (Mathematical Chemistry), Routledge. [1st ed.]."},{"key":"ref_18","first-page":"29","article-title":"Exponential vertex\u2013degree\u2013based topological indices and discrimination","volume":"82","author":"Rada","year":"2019","journal-title":"Math. Comput. Chem."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1515\/chem-2019-0007","article-title":"Zagreb connection number index of nanotubes and regular hexagonal lattice","volume":"17","author":"Ye","year":"2019","journal-title":"Open Chem."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Gao, W., Siddiqui, M., Naeem, M., and Rehman, N. (2017). Topological Characterization of Carbon Graphite and Crystal Cubic Carbon Structures. Molecules, 22.","DOI":"10.3390\/molecules22091496"},{"key":"ref_21","first-page":"143","article-title":"Molecular descriptors of benzenoid systems","volume":"40","author":"Idrees","year":"2016","journal-title":"Quim. Nova"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jpdc.1995.1002","article-title":"Distributed Loop Computer-Networks: A Survey","volume":"24","author":"Bermond","year":"1995","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(00)00243-7","article-title":"A complementary survey on double-loop networks","volume":"263","author":"Hwang","year":"2001","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0304-3975(01)00341-3","article-title":"A survey on multi-loop networks","volume":"299","author":"Hwang","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0169-7552(86)90027-9","article-title":"A survey of multi-connected loop topologies for local computer networks","volume":"11","author":"Raghavendra","year":"1986","journal-title":"Comput. Netw. ISDN Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1109\/TCOM.1972.1091214","article-title":"Analysis and Design of Reliable Computer Networks","volume":"20","author":"Wilkov","year":"1972","journal-title":"IEEE Trans. Commun."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1109\/PROC.1972.8647","article-title":"The Illiac IV system","volume":"60","author":"Bouknight","year":"1972","journal-title":"Proc. IEEE"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Bonchev, D., and Mekenyan, O. (1994). Graph Theoretical Approaches to Chemical Reactivity, Springer.","DOI":"10.1007\/978-94-011-1202-4"},{"key":"ref_29","first-page":"73","article-title":"Broadcasting in small-world communication networks","volume":"85","author":"Comellas","year":"2002","journal-title":"Sirocco"},{"key":"ref_30","unstructured":"Muga, F.P., and Yu, W.E.S. (2000, January 1). A Proposed Topology for a 192-Processor Symmetric Cluster with a Single-Switch Delay. Proceedings of the First Philippine Computing Science Congress, Manila, Philippines."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s00453-001-0043-5","article-title":"All-to-All Optical Routing in Chordal Rings of Degree 4","volume":"31","author":"Narayanan","year":"2001","journal-title":"Algorithmica"},{"key":"ref_32","first-page":"132","article-title":"Cellular neural networks with circulant graphs","volume":"3","author":"Nesterenko","year":"2009","journal-title":"Artif. Intell."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Alspach, B., and Varma, B.N. (1980). Decomposing Complete Graphs Into Cycles of Length 2P. Annals of Discrete Mathematics, Elsevier.","DOI":"10.1016\/S0167-5060(08)70053-0"},{"key":"ref_34","unstructured":"Bos\u00e1k, J. (1990). Decompositions of Graphs, Springer."},{"key":"ref_35","first-page":"119","article-title":"Graph decomposition","volume":"45","author":"Rodger","year":"1990","journal-title":"Le Mat."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0012-365X(84)90096-7","article-title":"Research problems","volume":"52","author":"Alspach","year":"1984","journal-title":"Discrete Math."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/0095-8956(89)90040-3","article-title":"Hamiltonian decomposition of Cayley graphs of degree 4","volume":"46","author":"Bermond","year":"1989","journal-title":"J. Comb. Theory Ser. B."},{"key":"ref_38","first-page":"297","article-title":"Hamiltonian decomposition of recursive circulants","volume":"1533","author":"Park","year":"1998","journal-title":"Alg. Comput. ISAAC 1998 Lect. Notes Comput. Sci."},{"key":"ref_39","unstructured":"Davis, P.J. (1979). Circulant Matrices, Wiley."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"11267","DOI":"10.1016\/j.aej.2022.04.022","article-title":"On infinite circulant-balanced complete multipartite graphs decompotions based on generalized algorithmic approaches","volume":"61","author":"Bazighifan","year":"2022","journal-title":"Alex. Eng. J."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"8263","DOI":"10.1016\/j.aej.2022.01.049","article-title":"On the decomposition of circulant graphs using algorithmic approaches","volume":"61","author":"Hamed","year":"2022","journal-title":"Alex. Eng. J."},{"key":"ref_42","unstructured":"Peterson, L., and Davie, B. (2021). Computer Networks: A Systems Approach. Morgan Kaufmann Publishers. [6th ed.]."},{"key":"ref_43","unstructured":"Dally, W.J., and Towles, B.P. (2003). Principles and Practices of Interconnection Networks, Elsevier."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"e01516","DOI":"10.1016\/j.heliyon.2019.e01516","article-title":"Development of routing algorithms in networks-on-chip based on ring circulant topologies","volume":"5","author":"Romanov","year":"2019","journal-title":"Heliyon"},{"key":"ref_45","unstructured":"Concer, N. (2009). Design and Performance Evaluation of Network-on-Chip Communication Protocols and Architectures, University of Bologna."},{"key":"ref_46","first-page":"14","article-title":"NoC routing protocols\u2014Objective-based classification","volume":"66\u201367","author":"Koudil","year":"2016","journal-title":"J. Syst. Archit."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1016","DOI":"10.1109\/TVLSI.2019.2959618","article-title":"Formal Modeling of Network-on-Chip Using CFSM and its Application in Detecting Deadlock","volume":"28","author":"Das","year":"2020","journal-title":"IEEE Trans. Very Large Scale Integr. Syst."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Monakhova, E.A., Monakhov, O.G., and Romanov, A.Y. (2022). Routing Algorithms in Optimal Degree Four Circulant Networks Based on Relative Addressing: Comparative Analysis for Networks-on-Chip. IEEE Trans. Netw. Sci. Eng.","DOI":"10.1109\/TNSE.2022.3211985"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"13491","DOI":"10.1007\/s11227-022-04396-5","article-title":"Optimal circulant graphs as low-latency network topologies","volume":"78","author":"Huang","year":"2022","journal-title":"J. Supercomput."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Ditzel, D., Espasa, R., Aymerich, N., Baum, A., Berg, T., Burr, J., Hao, E., Iyer, J., Izquierdo, M., and Jayaratnam, S. (2021, January 22\u201324). Accelerating ML Recommendation with over a Thousand RISC-V\/Tensor Processors on Esperanto\u2019s ET-SoC-1 Chip. Proceedings of the 2021 IEEE Hot Chips 33 Symposium (HCS), Palo Alto, CA, USA.","DOI":"10.1109\/HCS52781.2021.9566904"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Rocki, K., Van Essendelft, D., Sharapov, I., Schreiber, R., Morrison, M., Kibardin, V., Portnoy, A., Dietiker, J.F., Syamlal, M., and James, M. (2020, January 9\u201319). Fast Stencil-Code Computation on a Wafer-Scale Processor. Proceedings of the SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, Atlanta, GA, USA.","DOI":"10.1109\/SC41405.2020.00062"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Rzaev, E., Ryzhov, A., and Romanov, A. (2022, January 16\u201320). The New Promising Network-on-Chip Topologies Development Using Hierarchical Method. Proceedings of the 2022 International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM), Sochi, Russia.","DOI":"10.1109\/ICIEAM54945.2022.9787143"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"1255","DOI":"10.1007\/s11036-019-01262-2","article-title":"SCCN: A Time-Effective Hierarchical Interconnection Network for Network-On-Chip","volume":"24","author":"Ali","year":"2019","journal-title":"Mob. Netw. Appl."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"99249","DOI":"10.1109\/ACCESS.2021.3095146","article-title":"The Static Performance Effect of Hybrid- Hierarchical Interconnection by Shifted Completely Connected Network","volume":"9","author":"Ali","year":"2021","journal-title":"IEEE Access"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Rzaev, E.R., and Romanov, A.Y. (2021, January 5\u201311). The New Promising Network-on-Chip Topologies Development Using Product Operation. Proceedings of the 2021 International Russian Automation Conference (RusAutoCon), Sochi, Russia.","DOI":"10.1109\/RusAutoCon52004.2021.9537317"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/10\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:48:12Z","timestamp":1760147292000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,22]]},"references-count":55,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["a16010010"],"URL":"https:\/\/doi.org\/10.3390\/a16010010","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,22]]}}}