Original title:
Barvení grafů pomocí mravenčí kolonie
Translated title:
Barvení grafů pomocí mravenčí kolonie
Authors:
Vámošová, Mária ; Lidický, Bernard (referee) ; Jelínková, Eva (advisor) Document type: Bachelor's theses
Year:
2010
Language:
eng Abstract:
[eng][cze] In the present thesis we deal with the Graph Coloring Problem. We provide an overview of the existing approaches and focus on the Ant Colony Optimization heuristics. We have selected three algorithms, implemented them and performed a set of tests on several commonly used graph instances to study their advantages and drawbacks. We also compared their results to the best known at time to nd out how much they are suitable for the problem. In this thesis we also present an original algorithm.V této práci se zabýváme problémem barvení grafů. Podáváme přehled existujích algoritmů a zaměřujeme se na algoritmy mravenční kolonie. Pro pozorování jejich principů a provnání jsme vybrali tř esistující algoritmy, otestovali je na známých grafecz a podáváme přehled výsledků. Tyto výsledky jsou dále porovnávnány s dosud nejlepšími známými. Součástí práce je i návrh otestování vlastního algoritmu.
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/28803