Frontové rozklady grafů
| Thesis title in Czech: | Frontové rozklady grafů |
|---|---|
| Thesis title in English: | Queue layouts of graphs |
| Academic year of topic announcement: | 2012/2013 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | doc. Mgr. Petr Gregor, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 01.11.2012 |
| Date of assignment: | 01.11.2012 |
| Confirmed by Study dept. on: | 23.11.2012 |
| Guidelines |
| 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ů. |
| References |
| [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. |