Modelirovanie i Analiz Informatsionnykh Sistem
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Modelirovanie i Analiz Informatsionnykh Sistem, 2021, Volume 28, Number 2, Pages 126–135
DOI: https://doi.org/10.18255/1818-1015-2021-2-126-135
(Mi mais739)
 

Algorithms

Identification conditions for the solvability of NP-complete problems for the class of pre-fractal graphs

A. V. Tymoshenkoa, R. A. Kochkarovb, A. A. Kochkarovb

a National Research University of Electronic Technology (MIET), 1 Shokin Square, Zelenograd 124498, Russia
b Financial University under the Government of the Russian Federation, 49 Leningradsky Prospekt, Moscow 125993, Russia
References:
Abstract: 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.
Funding agency Grant number
Russian Science Foundation 21-19-00481
The study was supported by a grant from the Russian Science Foundation No. 21-19-00481.
Received: 09.03.2021
Revised: 27.04.2021
Accepted: 12.05.2021
Document Type: Article
UDC: 519.17
Language: Russian
Citation: 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”, Model. Anal. Inform. Sist., 28:2 (2021), 126–135
Citation in format AMSBIB
\Bibitem{TymKocKoc21}
\by A.~V.~Tymoshenko, R.~A.~Kochkarov, A.~A.~Kochkarov
\paper Identification conditions for the solvability of NP-complete problems for the class of pre-fractal graphs
\jour Model. Anal. Inform. Sist.
\yr 2021
\vol 28
\issue 2
\pages 126--135
\mathnet{http://mi.mathnet.ru/mais739}
\crossref{https://doi.org/10.18255/1818-1015-2021-2-126-135}
Linking options:
  • https://www.mathnet.ru/eng/mais739
  • https://www.mathnet.ru/eng/mais/v28/i2/p126
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
    Statistics & downloads:
    Abstract page:116
    Full-text PDF :44
    References:23
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024