Identyfikatory
Warianty tytułu
Graph colouring algorithms
Języki publikacji
Abstrakty
Głównym celem pracy było zbadanie algorytmów rozwiązujących problem kolorowania grafu, kolejno: algorytmów zachłannych LF (ang. Largest First) i SFL (ang. Saturated Largest First), algorytmu genetycznego sekwencyjnego oraz równoległego. Ponadto, zaimplementowana została aplikacja działającej w środowisku przeglądarki internetowej pozwalająca na wizualizacje 3D procesu kolorowania grafu wraz z regulacją parametrów grafu (takich jak liczba wierzchołków i gęstość grafu) oraz obserwację uzyskanych wyników (czasu wykonywania algorytmu i liczby dobranych kolorów).
The main aim of the study was to examine four algorithms concerning the graph colouring problem, respectively: LF (Largest First), SFL (Saturated Largest First), genetic algorithm, both sequential and multithreaded. Additionally, an application in a web browser environment was created to 3D visualisation of the graph colouring process allowing adjustment of graph parameters (such as number of vertices and graph density) and observation of the obtained results (execution time and number of colours).
Rocznik
Tom
Strony
85--97
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
autor
- Politechnika Śląska, Wydział Elektryczny, Instytut Elektrotechniki i Informatyki, Akademicka 10, 44-100, Gliwice
autor
- Politechnika Śląska, Wydział Elektryczny, Instytut Elektrotechniki i Informatyki, Akademicka 10, 44-100, Gliwice
Bibliografia
- 1. Figielska E. „Algorytmy ewolucyjne i ich zastosowania”, Biblioteka Narodowa, 2006
- 2. https://pl.wikipedia.org/wiki/Proble_NP-zupełny
- 3. https://pl.wikipedia.org/wiki/Twierdzenie_o_czterech_barwach
- 4. https://graphtheoryinlatex.wordpress.com/2010/02/18/a-coloring-of-the-petersen-graph-2/
- 5. https://en.wikipedia.org/wiki/Master/slave_(technology)
- 6. https://pl.wikipedia.org/wiki/Mediator_(wzorzec_projektowy)
- 7. https://msdn.microsoft.com/pl-pl/library/ee850490(v=vs.110).aspx
- 8. http://blog.helion.pl/wzorzec-projektowy-strategii/
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-f650d7da-dbb4-43d2-b5a9-57427d9cab97