Równoległy algorytm do testowania cięciwowości grafów

Graf G jest cięciwowy jeśli każdy cykl o rozmiarze większym od 3 w G ma cięciwę, to jest krawędź pomiędzy dwoma niesąsiednimi wierzchołkami w cyklu. W naszej pracy prezentujemy prosty algorytm równoległy do testowania cięciwowości grafów. Podstawą tego algorytmu jest znajdowanie porządku LexBFS danego grafu. Cały algorytm działa w czasie O(N) na N wątkowej maszynie i wykonuje pracę O(N^2), gdzie N jest liczbą wierzchołków w grafie. Nasza implementacja wykorzystuje uniwersalną architekturę procesorów wielordzeniowych CUDA C firmy Nvidia. Na końcu pracy prezentujemy wyniki testów implementacji równoległej i porównujemy je z wynikami implementacji sekwencyjnej.

A graph is chordal if each cycle of size greater than 3 in G has a chord, that is an edge between two non-adjacent vertices in the cycle. In our work we present a simple parallel algorithm to test chordality of graphs which is based on the parallel Lexicographical Breadth-First Search algorithm. In total, the algorithm takes time O(N) on N -threads machine and it performs work O(N^2), where N is the number of vertices in a graph. Our implementation of the algorithm uses a GPU environment Nvidia CUDA C. At the end of the thesis we present the results achieved by our implementation and compare them with the results achieved by the sequential algorithm.