Frontové rozklady grafů
| Název práce v češtině: | Frontové rozklady grafů |
|---|---|
| Název v anglickém jazyce: | Queue layouts of graphs |
| Akademický rok vypsání: | 2012/2013 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | doc. Mgr. Petr Gregor, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 01.11.2012 |
| Datum zadání: | 01.11.2012 |
| Datum potvrzení stud. oddělením: | 23.11.2012 |
| Zásady pro vypracování |
| Frontový rozklad grafu je lineární uspořádání vrcholů a rozklad množiny hran na podmnožiny, zvané fronty, v nichž žádná hrana není vnořena (vzhledem k zvolenému uspořádání) pod jinou hranu. Frontové rozklady mají využití pro paralelní rozvrhování, třídění permutací, kreslení grafů a výpočty na počítačích s rychlým zpracováním front.
Cílem práce je seznámit se s problematikou frontových rozkladů, prozkoumat vztah mezi počtem front a jejich velikostí u dosud známých frontových rozkladů a pokusit se zobecnit nedávné výsledky pro dolní odhady na tzv. frontové číslo na nové třídy grafů. |
| Seznam odborné literatury |
| [1] V. Dujmovic, D. R. Wood, On linear layouts of graphs, Discrete. Math. Theor. Comput. Sci. 6 (2004), 497-522.
[2] P. Gregor, R. Škrekovski, V. Vukašenovic, Queue layouts of hypercubes, SIAM J. Discrete Math. 26 (2012), 77-88. [3] L. S. Heath, A. L. Rosenberg, Laying out graphs using queues, SIAM J. Comput. 21 (1992), 927-958. [4] D. R. Wood, Queue layouts of graph products and powers, Discrete. Math. Theor. Comput. Sci. 7 (2005), 255-268. |