По-русски
Biography
Master's
work
Library
Links
Search
results
Viatcheslav Kourktchi
kourktchi@ukrtop.com
master's degree competitor (faculty of computer engineering and computer science)
research teacher:
Yuri Ladyzhensky
master's work topic:
Parallel algorithms for graph problems solving.
Full version [pdf - in russian] (212 kb)
Introduction
The graphs are the very widespread data structure, and the problems connected to them, find the application in various areas of science and engineering: these problems are solved in large-scale integrated circuit designing, in making parallel computing and other processes, in organization of associative memory, in the theory of final automatic devices, flows in networks etc. Problems on the graphs many from us frequently solve in a daily life, not knowing at all about it.
Unfortunately, the large part of problems on graphs is NP-complete, that largely complicates search of the decision. However frequently problems of such class are necessary to be solved. It has caused occurrence of the direction that study approached, or heuristic, algorithms. The large part of NP-complete problems is reduced to linear programming that allows using in quality the decision any local maxima (minima). Such decision, certainly, is not optimum, but is allowable.
The process of the decision of a problem of large dimension even by the approached algorithm can be rather long, that is fair for all problems and any algorithms. For acceleration of search of the decisions, researchers use parallel algorithms. The temporary complexity of parallel algorithms is usual, lower to the order, than similar consecutive, and sometimes it can be concerned to other classes of problem.
The maximum independent set problem was chosen to be considered. This task was chosen for two reasons. First, it is fundamental, and it is related with next problems: minimum covering, maximum edge independent set, minimum dominating set and many others. That is the majority of algorithms for the decision of this problem is possible to distribute on many others. Secondly, this problem has rather big number of applications that makes search of effective algorithm for the decision of this problem necessary. By virtue of last, The maximum independent set problem has become recently very popular among the researchers.
The subset of vertices of the graph is independent, if any two vertices from this set are not adjacent.
Example of independent set on a graph.
