Algorithms of graph partitioning

Problem podziału grafu jest jednym z podstawowych zadań w informatyce i ma wiele zastosowań, np. w symulacjach naukowych, sieciach społecznościowych, czy przy projektowaniu układów scalonych bądź przy obliczeniach równoległych. Niestety znalezienie optymalnego podziału grafu należy do klasy problemów NP-zupełnych. Niemniej jednak w ostatnich latach opracowano wiele skutecznych heurystyk. Problem ten występuje w dwóch wersjach, w podstawowej wersji szukamy krawędzi grafu, których usunięcie rozspójnia graf, a w drugiej wierzchołków.W tej pracy postaram się przedstawić metody, jakimi próbowano rozwiązać ten problem na początku, ponieważ pomimo upływu lat niektóre metody są dalej stosowane. Zaprezentuję, także algorytm szukający separatorów wierzchołków. Następnie pokażę kombinatoryczne podejście do problemu podziału grafu oraz opiszę najlepszą obecnie metodę stosowaną do podziału grafu, a więc metodę wielopoziomową, a na koniec przedstawię rezultaty, jakie osiągnęły moje implementacje oraz porównam je z wynikami osiągniętymi przez bibliotekę MeTiS.The problem of graph partitioning is one of the basic tasks in computer science and has many applications, e.g. in scientific simulations, social networks, or in the design of integrated circuits or parallel calculations. Unfortunately, finding the optimal partitions belongs to the class of NP-complete problems. Nevertheless, many effective heuristics have been developed in recent years. This problem occurs in two versions, in the basic version we are looking for the edges of the graph, whose removal separates the graph, and in the second vertices. In this work I will try to present the methods that tried to solve this problem at the beginning, because despite the passage of years some methods are still used. I will also present an algorithm looking for vertex separators. Next, I will show a combinatorial approach to the problem of graph division and describe the currently best method used to graph partitioning is multilevel method, and finally I will present the results achieved by my implementations and compare them with the results achieved by the MeTiS library