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...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
MDPI AG
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/5558703dc42545828ee9286aa8d74e09 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| id |
oai:doaj.org-article:5558703dc42545828ee9286aa8d74e09 |
|---|---|
| record_format |
dspace |
| spelling |
oai:doaj.org-article:5558703dc42545828ee9286aa8d74e092021-11-11T18:18:27ZResearch of NP-Complete Problems in the Class of Prefractal Graphs10.3390/math92127642227-7390https://doaj.org/article/5558703dc42545828ee9286aa8d74e092021-10-01T00:00:00Zhttps://www.mdpi.com/2227-7390/9/21/2764https://doaj.org/toc/2227-7390NP-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.Rasul KochkarovMDPI AGarticleNP-complete problemsprefractal graphssubgraph search algorithmsMathematicsQA1-939ENMathematics, Vol 9, Iss 2764, p 2764 (2021) |
| institution |
DOAJ |
| collection |
DOAJ |
| language |
EN |
| topic |
NP-complete problems prefractal graphs subgraph search algorithms Mathematics QA1-939 |
| spellingShingle |
NP-complete problems prefractal graphs subgraph search algorithms Mathematics QA1-939 Rasul Kochkarov Research of NP-Complete Problems in the Class of Prefractal Graphs |
| 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. |
| format |
article |
| author |
Rasul Kochkarov |
| author_facet |
Rasul Kochkarov |
| author_sort |
Rasul Kochkarov |
| title |
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_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_sort |
research of np-complete problems in the class of prefractal graphs |
| publisher |
MDPI AG |
| publishDate |
2021 |
| url |
https://doaj.org/article/5558703dc42545828ee9286aa8d74e09 |
| work_keys_str_mv |
AT rasulkochkarov researchofnpcompleteproblemsintheclassofprefractalgraphs |
| _version_ |
1718431885038714880 |