Barvení grafů pomocí mravenčí kolonie

• Název práce v češtině: Barvení grafů pomocí mravenčí kolonie
• Název v anglickém jazyce: Graph Coloring Using an Ant Colony
• Akademický rok vypsání: 2008/2009
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: RNDr. Mgr. Eva Jelínková, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 09.10.2008
• Datum zadání: 09.10.2008
• Datum a čas obhajoby: 22.06.2010 00:00
• Datum odevzdání elektronické podoby: 22.06.2010
• Datum proběhlé obhajoby: 22.06.2010
• Oponenti: RNDr. Bernard Lidický, Ph.D.

Zásady pro vypracování

Studentka se seznámí s existujícími algoritmy pro barvení grafů pomocí mravenčí kolonie a implementuje vybrané z nich. Studentka vypracuje přehled vybraných algoritmů a jejich srovnání. Dále se případně pokusí navrhnout a implementovat vlastní algoritmus nebo vylepšení algoritmu existujícího.

Seznam odborné literatury

K. A. Dowsland, J. M. Thompson: An improved ant colony optimisation heuristic for graph colouring. Discrete Applied Mathematics 156 (2004), pp. 313-324.
T. N. Buia, T. H. Nguyen, C. M. Patel, K.-A. T. Phan: An ant-based algorithm for coloring graphs. Discrete Applied Mathematics 154 (2008), pp. 190-200.
A. Hertz, N. Zufferey: A New Ant Algorithm for Graph Coloring. Proceedings of NICSO 2006, Granada, Spain, pp. 51-60.
A další literatura podle pokynů vedoucí.

Předběžná náplň práce

Cílem práce je implementovat některé existující algoritmy pro barvení grafů pomocí mravenčí kolonie a podat jejich přehled a srovnání. Práce také může obsahovat návrh a implementaci vlastního algoritmu nebo vylepšení algoritmu existujícího.

Předběžná náplň práce v anglickém jazyce

The aim of the thesis is to implement several existing algorithms for graph coloring using an ant colony, and to give their overview and comparison. The thesis may also contain a design and implementation of an original algorithm or an improvement of an existing one.