Optimalizační úlohy barvení grafů s náhodnými prvky
| Název práce v češtině: | Optimalizační úlohy barvení grafů s náhodnými prvky |
|---|---|
| Název v anglickém jazyce: | Optimization problems of vertex coloring under uncertainty |
| Klíčová slova: | Optimalizační úloha barvení grafu s náhodnými prvky, celočíselná lineární formulace s omezeními, celočíselná kvadratická formulace bez omezení |
| Klíčová slova anglicky: | Optimization problems of vertex coloring under uncertainty, integer linear formulation with constraints, integer quadratic formulation without constraints |
| Akademický rok vypsání: | 2013/2014 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra pravděpodobnosti a matematické statistiky (32-KPMS) |
| Vedoucí / školitel: | doc. RNDr. Martin Branda, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 26.09.2013 |
| Datum zadání: | 26.09.2013 |
| Datum potvrzení stud. oddělením: | 25.11.2013 |
| Datum a čas obhajoby: | 03.09.2014 00:00 |
| Datum odevzdání elektronické podoby: | 30.07.2014 |
| Datum odevzdání tištěné podoby: | 31.07.2014 |
| Datum proběhlé obhajoby: | 03.09.2014 |
| Oponenti: | doc. RNDr. Petr Lachout, CSc. |
| Zásady pro vypracování |
| Úloha barvení vrcholů grafu neslouží pouze k barvení map, ale nachází své aplikace například i v segmentaci nebo rozvrhování. Řešitel(ka) se seznámí se dvěma formulacemi úlohy s náhodnými hranami ve tvaru optimalizačních problémů - lineárním celočíselným s omezeními a kvadratickým celočíselným bez dalších omezení. Tyto formulace poté porovná v numerické studii za využití vhodného optimalizačního softwaru. |
| Seznam odborné literatury |
| J. Yanez, J. Ramirez, The robust coloring problem. European Journal of Operational Research 148 (2003) 546--558.
F. Wang, Z. Xu, Metaheuristics for robust graph coloring. Journal of Heuristics 19 (2013) 529--548. L.A. Wolsey, G.L. Nemhauser, Integer and Combinatorial Optimization. Wiley, New York, 1999. |