
StatusThe thesis was presented on the 23 March, 2017Approved by NCAA on the 31 May, 2017 Abstract– 0.76 Mb / in romanianThesisCZU 519.83
3.58 Mb /
in romanian 
The thesis has been elaborated in Moldova State University, Chisinau, 2017.
Thesis structure: The thesis is written in romanian language and contains an introduction, three chapters, general conclusions and recommendations, a bibliography of 115 titles, 122 pages of main text. The obtained results were published in 12 scientific papers.
The field of study: Graph theory
The aim of the research. The purpose of this PhD thesis is to study the problem of covering undirected graphs by dconvex sets. To achieve the purpose the following objectives are fixed: studying complexity of the problem of covering graphs by 2 p dconvex sets; establishing conditions of existence of a dconvex set family covering an undirected graph; solving the problem of graph covering by nontrivial dconvex sets; developing algorithms for the problem of graph cover/partition by dconvex sets; determining the minimum/maximum dconvex cover number.
The scientific novelty and originality is reflected in obtaining theoretical and applied results which have supplemented and generalized known results related to graph cover by dconvex sets and in proving of NPcompletness of the graph dconvex cover problem and some of its variations.
Important scientific problem solved in the research consists in proving of NPcompleteness of nonoriented graph cover/partition by dconvex sets, which leads to the need to study conditions for existence of p 2 dconvex sets family, that cover/partition some graph classes for further implementation of methods and efficient algorithms for solving applied problems.
The theoretical significance of the research is determined by results associated with NPcompleteness of graphs cover by two dconvex sets problem, which complements results in the field of study, obtained by other mathematicians . Also, it has been proven that the problems of general graphs cover by dconvex sets problem and graphs cover by nontrivial dconvex sets problem are NPcomplete.
The applicative value of the paper consists in possibility of using obtained results for studying dconvex sets on discrete structures and in obtaining of algorithms for graphs cover/partition by dconvex sets problem, which can solve the investigated problem for practical applications, for example, for the task of clustering elements of a set with a binary relation defined over its elements.
The implementation of the scientific results. The results can be used in development of specialized courses for university students related to optimization problems on discrete structures. The developed algorithms are implemented as a library, written in C# programming language.
Under consideration [1] :
Theses Archive: