Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs
Modern network systems (unmanned aerial vehicles groups, social networks, network production chains, transport and logistics networks, communication networks, cryptocurrency networks) are distinguished by their multi-element nature and the dynamics of connections between its elements. A number of di...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2021-06-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1483 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839573225083764736 |
|---|---|
| author | Aleksandr Vasil'evich Tymoshenko Rasul Ahmatovich Kochkarov Azret Ahmatovich Kochkarov |
| author_facet | Aleksandr Vasil'evich Tymoshenko Rasul Ahmatovich Kochkarov Azret Ahmatovich Kochkarov |
| author_sort | Aleksandr Vasil'evich Tymoshenko |
| collection | DOAJ |
| description | Modern network systems (unmanned aerial vehicles groups, social networks, network production chains, transport and logistics networks, communication networks, cryptocurrency networks) are distinguished by their multi-element nature and the dynamics of connections between its elements. A number of discrete problems on the construction of optimal substructures of network systems described in the form of various classes of graphs are NP-complete problems. In this case, the variability and dynamism of the structures of network systems leads to an "additional" complication of the search for solutions to discrete optimization problems. At the same time, for some subclasses of dynamical graphs, which are used to model the structures of network systems, conditions for the solvability of a number of NP-complete problems can be distinguished. This subclass of dynamic graphs includes pre-fractal graphs. The article investigates NP-complete problems on pre-fractal graphs: a Hamiltonian cycle, a skeleton with the maximum number of pendant vertices, a monochromatic triangle, a clique, an independent set. The conditions under which for some problems it is possible to obtain an answer about the existence and to construct polynomial (when fixing the number of seed vertices) algorithms for finding solutions are identified. |
| format | Article |
| id | doaj-art-a8fcb3e526b34e76a8676be2cd0c3cbc |
| institution | Matheson Library |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2021-06-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-a8fcb3e526b34e76a8676be2cd0c3cbc2025-08-04T14:06:42ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172021-06-0128212613510.18255/1818-1015-2021-2-126-1351126Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal GraphsAleksandr Vasil'evich Tymoshenko0Rasul Ahmatovich Kochkarov1Azret Ahmatovich Kochkarov2National Research University of Electronic Technology (MIET)Financial University under the Government of the Russian FederationFinancial University under the Government of the Russian FederationModern network systems (unmanned aerial vehicles groups, social networks, network production chains, transport and logistics networks, communication networks, cryptocurrency networks) are distinguished by their multi-element nature and the dynamics of connections between its elements. A number of discrete problems on the construction of optimal substructures of network systems described in the form of various classes of graphs are NP-complete problems. In this case, the variability and dynamism of the structures of network systems leads to an "additional" complication of the search for solutions to discrete optimization problems. At the same time, for some subclasses of dynamical graphs, which are used to model the structures of network systems, conditions for the solvability of a number of NP-complete problems can be distinguished. This subclass of dynamic graphs includes pre-fractal graphs. The article investigates NP-complete problems on pre-fractal graphs: a Hamiltonian cycle, a skeleton with the maximum number of pendant vertices, a monochromatic triangle, a clique, an independent set. The conditions under which for some problems it is possible to obtain an answer about the existence and to construct polynomial (when fixing the number of seed vertices) algorithms for finding solutions are identified.https://www.mais-journal.ru/jour/article/view/1483np-complete problemspre-fractal graphsdiscrete problemssolvability conditions |
| spellingShingle | Aleksandr Vasil'evich Tymoshenko Rasul Ahmatovich Kochkarov Azret Ahmatovich Kochkarov Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs Моделирование и анализ информационных систем np-complete problems pre-fractal graphs discrete problems solvability conditions |
| title | Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs |
| title_full | Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs |
| title_fullStr | Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs |
| title_full_unstemmed | Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs |
| title_short | Identification Conditions for the Solvability of NP-complete Problems for the Class of Pre-fractal Graphs |
| title_sort | identification conditions for the solvability of np complete problems for the class of pre fractal graphs |
| topic | np-complete problems pre-fractal graphs discrete problems solvability conditions |
| url | https://www.mais-journal.ru/jour/article/view/1483 |
| work_keys_str_mv | AT aleksandrvasilevichtymoshenko identificationconditionsforthesolvabilityofnpcompleteproblemsfortheclassofprefractalgraphs AT rasulahmatovichkochkarov identificationconditionsforthesolvabilityofnpcompleteproblemsfortheclassofprefractalgraphs AT azretahmatovichkochkarov identificationconditionsforthesolvabilityofnpcompleteproblemsfortheclassofprefractalgraphs |