Research of NP-Complete Problems in the Class of Prefractal Graphs
NP-complete problems in graphs, such as enumeration and the selection of subgraphs with given characteristics, become especially relevant for large graphs and networks. Herein, particular statements with constraints are proposed to solve such problems, and subclasses of graphs are distinguished. We...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/21/2764 |
| _version_ | 1797512074788601856 |
|---|---|
| author | Rasul Kochkarov |
| author_facet | Rasul Kochkarov |
| author_sort | Rasul Kochkarov |
| collection | DOAJ |
| description | NP-complete problems in graphs, such as enumeration and the selection of subgraphs with given characteristics, become especially relevant for large graphs and networks. Herein, particular statements with constraints are proposed to solve such problems, and subclasses of graphs are distinguished. We propose a class of prefractal graphs and review particular statements of NP-complete problems. As an example, algorithms for searching for spanning trees and packing bipartite graphs are proposed. The developed algorithms are polynomial and based on well-known algorithms and are used in the form of procedures. We propose to use the class of prefractal graphs as a tool for studying NP-complete problems and identifying conditions for their solvability. Using prefractal graphs for the modeling of large graphs and networks, it is possible to obtain approximate solutions, and some exact solutions, for problems on natural objects—social networks, transport networks, etc. |
| first_indexed | 2024-03-10T05:56:46Z |
| format | Article |
| id | doaj.art-5558703dc42545828ee9286aa8d74e09 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T05:56:46Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-5558703dc42545828ee9286aa8d74e092023-11-22T21:18:31ZengMDPI AGMathematics2227-73902021-10-01921276410.3390/math9212764Research of NP-Complete Problems in the Class of Prefractal GraphsRasul Kochkarov0Department of Data Analysis and Machine Learning, Faculty of Information Technology and Big Data Analysis, Financial University under the Government of the Russian Federation, Leningradsky Prospekt, 49, 125993 Moscow, RussiaNP-complete problems in graphs, such as enumeration and the selection of subgraphs with given characteristics, become especially relevant for large graphs and networks. Herein, particular statements with constraints are proposed to solve such problems, and subclasses of graphs are distinguished. We propose a class of prefractal graphs and review particular statements of NP-complete problems. As an example, algorithms for searching for spanning trees and packing bipartite graphs are proposed. The developed algorithms are polynomial and based on well-known algorithms and are used in the form of procedures. We propose to use the class of prefractal graphs as a tool for studying NP-complete problems and identifying conditions for their solvability. Using prefractal graphs for the modeling of large graphs and networks, it is possible to obtain approximate solutions, and some exact solutions, for problems on natural objects—social networks, transport networks, etc.https://www.mdpi.com/2227-7390/9/21/2764NP-complete problemsprefractal graphssubgraph search algorithms |
| spellingShingle | Rasul Kochkarov Research of NP-Complete Problems in the Class of Prefractal Graphs Mathematics NP-complete problems prefractal graphs subgraph search algorithms |
| title | Research of NP-Complete Problems in the Class of Prefractal Graphs |
| title_full | Research of NP-Complete Problems in the Class of Prefractal Graphs |
| title_fullStr | Research of NP-Complete Problems in the Class of Prefractal Graphs |
| title_full_unstemmed | Research of NP-Complete Problems in the Class of Prefractal Graphs |
| title_short | Research of NP-Complete Problems in the Class of Prefractal Graphs |
| title_sort | research of np complete problems in the class of prefractal graphs |
| topic | NP-complete problems prefractal graphs subgraph search algorithms |
| url | https://www.mdpi.com/2227-7390/9/21/2764 |
| work_keys_str_mv | AT rasulkochkarov researchofnpcompleteproblemsintheclassofprefractalgraphs |