Geodesic
Identification conditions for the solvability of NP-complete problems for the class of pre-fractal graphs
Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 2, pp. 126-135.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: NP-complete problems, pre-fractal graphs, discrete problems, solvability conditions. 
@article{MAIS_2021_28_2_a0,
     author = {A. V. Tymoshenko and R. A. Kochkarov and A. A. Kochkarov},
     title = {Identification conditions for the solvability of {NP-complete} problems for the class of pre-fractal graphs},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {126--135},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2021_28_2_a0/}
}
TY  - JOUR
AU  - A. V. Tymoshenko
AU  - R. A. Kochkarov
AU  - A. A. Kochkarov
TI  - Identification conditions for the solvability of NP-complete problems for the class of pre-fractal graphs
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2021
SP  - 126
EP  - 135
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2021_28_2_a0/
LA  - ru
ID  - MAIS_2021_28_2_a0
ER  - 
%0 Journal Article
%A A. V. Tymoshenko
%A R. A. Kochkarov
%A A. A. Kochkarov
%T Identification conditions for the solvability of NP-complete problems for the class of pre-fractal graphs
%J Modelirovanie i analiz informacionnyh sistem
%D 2021
%P 126-135
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2021_28_2_a0/
%G ru
%F MAIS_2021_28_2_a0
A. V. Tymoshenko; R. A. Kochkarov; A. A. Kochkarov. Identification conditions for the solvability of NP-complete problems for the class of pre-fractal graphs. Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 2, pp. 126-135. http://geodesic.mathdoc.fr/item/MAIS_2021_28_2_a0/

[1] A. Kochkarov, R. Kochkarov, G. Malinetskii, “Issues of dynamic graph theory”, Computational Mathematics and Mathematical Physics, 55:9 (2015), 1590–1596 | DOI | MR | Zbl

[2] S. Pupyrev, A. Tikhonov, “The analysis of complex networks with dynamic graph visualization”, Modeling and Analysis of Information Systems, 17:1 (2010), 117–135

[3] Y. Belov, S. Vovchok, “Generation of a social network graph by using apache spark”, Modeling and Analysis of Information Systems, 23:6 (2016), 777–783 | DOI | MR

[4] S. Morzhov, V. Sokolov, “An effective algorithm for collision resolution in security policy rules”, Modeling and Analysis of Information Systems, 26:1 (2019), 75–89 | DOI | MR

[5] A. M. Kochkarov, V. A. Perepelitsa, I. V. Sergienko, Recognition of fractal graphs. Algorithmic approach, RAS SAO, 1998

[6] R. A. Kochkarov, Problems of multicriteria optimization on multi-weighted prefractal graphs, Akademinnovatsiya, 2014, 319–328

[7] F. Harary, Graph theory, Addison-Wesley Pub. Co., 1969 | MR | Zbl

[8] M. A. Iordanskii, “Constructive classification of graphs”, Modeling and Analysis of Information Systems, 19:4 (2012), 144–153 | DOI

[9] M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of np-completeness, W. H. Freeman and Company, 1979 | MR | Zbl