A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks
Based on the analysis of a large dataset for optimal undirected double-loop networks, we studied the problem of finding families of optimal double-loop graphs with the minimal possible diameter. Optimal double-loop networks are of practical interest as graph models for reliable, low-delay communicat...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/11036794/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849421460176633856 |
|---|---|
| author | Emilia A. Monakhova Oleg G. Monakhov Edward R. Rzaev Aleksandr A. Amerikanov Mikhail Y. Romashikhin Aleksandr Y. Romanov |
| author_facet | Emilia A. Monakhova Oleg G. Monakhov Edward R. Rzaev Aleksandr A. Amerikanov Mikhail Y. Romashikhin Aleksandr Y. Romanov |
| author_sort | Emilia A. Monakhova |
| collection | DOAJ |
| description | Based on the analysis of a large dataset for optimal undirected double-loop networks, we studied the problem of finding families of optimal double-loop graphs with the minimal possible diameter. Optimal double-loop networks are of practical interest as graph models for reliable, low-delay communication in computer systems and networks-on-chip, due to their advantageous networking properties. A large dataset of optimal double-loop networks with up to 50000 nodes and all the optimal generators for given graph orders were built. We automated the process of searching for analytical (described by polynomials in diameter) descriptions of the families of optimal double-loop networks. After applying the integration of differential evolution methods, exhaustive local search, and a new search algorithm (based on the division of graph description polynomials) to the analysis of the generated dataset, we found a large amount of new (distinct from all previously known) families of optimal double-loop networks with generators of linear or quadratic types. Based on the analysis of the constructed dataset, a method for accelerated search for finding descriptions of optimal double-loop networks using second-order surface approximation was proposed. Our new approach can be used for the analysis of datasets of other promising classes of graphs and networks. |
| format | Article |
| id | doaj-art-ce68facab70048cbbf2ad6bd47e8fb8d |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-ce68facab70048cbbf2ad6bd47e8fb8d2025-08-20T03:31:27ZengIEEEIEEE Access2169-35362025-01-011310471610472710.1109/ACCESS.2025.357979011036794A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop NetworksEmilia A. Monakhova0https://orcid.org/0000-0002-6814-4655Oleg G. Monakhov1https://orcid.org/0000-0001-8316-418XEdward R. Rzaev2https://orcid.org/0000-0002-3504-7429Aleksandr A. Amerikanov3https://orcid.org/0000-0002-5970-2125Mikhail Y. Romashikhin4https://orcid.org/0009-0005-1604-3333Aleksandr Y. Romanov5https://orcid.org/0000-0002-9410-9431Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, RussiaInstitute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, RussiaHSE University, Moscow, RussiaHSE University, Moscow, RussiaHSE University, Moscow, RussiaHSE University, Moscow, RussiaBased on the analysis of a large dataset for optimal undirected double-loop networks, we studied the problem of finding families of optimal double-loop graphs with the minimal possible diameter. Optimal double-loop networks are of practical interest as graph models for reliable, low-delay communication in computer systems and networks-on-chip, due to their advantageous networking properties. A large dataset of optimal double-loop networks with up to 50000 nodes and all the optimal generators for given graph orders were built. We automated the process of searching for analytical (described by polynomials in diameter) descriptions of the families of optimal double-loop networks. After applying the integration of differential evolution methods, exhaustive local search, and a new search algorithm (based on the division of graph description polynomials) to the analysis of the generated dataset, we found a large amount of new (distinct from all previously known) families of optimal double-loop networks with generators of linear or quadratic types. Based on the analysis of the constructed dataset, a method for accelerated search for finding descriptions of optimal double-loop networks using second-order surface approximation was proposed. Our new approach can be used for the analysis of datasets of other promising classes of graphs and networks.https://ieeexplore.ieee.org/document/11036794/Optimal double-loop graphs datasetundirected double-loop networksfamilies of optimal circulant graphsanalytical descriptions of graph familiesnetworks-on-chip design |
| spellingShingle | Emilia A. Monakhova Oleg G. Monakhov Edward R. Rzaev Aleksandr A. Amerikanov Mikhail Y. Romashikhin Aleksandr Y. Romanov A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks IEEE Access Optimal double-loop graphs dataset undirected double-loop networks families of optimal circulant graphs analytical descriptions of graph families networks-on-chip design |
| title | A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks |
| title_full | A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks |
| title_fullStr | A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks |
| title_full_unstemmed | A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks |
| title_short | A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks |
| title_sort | new approach for automatic search for families of optimal undirected double loop networks |
| topic | Optimal double-loop graphs dataset undirected double-loop networks families of optimal circulant graphs analytical descriptions of graph families networks-on-chip design |
| url | https://ieeexplore.ieee.org/document/11036794/ |
| work_keys_str_mv | AT emiliaamonakhova anewapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT oleggmonakhov anewapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT edwardrrzaev anewapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT aleksandraamerikanov anewapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT mikhailyromashikhin anewapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT aleksandryromanov anewapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT emiliaamonakhova newapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT oleggmonakhov newapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT edwardrrzaev newapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT aleksandraamerikanov newapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT mikhailyromashikhin newapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks AT aleksandryromanov newapproachforautomaticsearchforfamiliesofoptimalundirecteddoubleloopnetworks |