Rozklady propojovacích sítí na dlouhé cesty
| Název práce v češtině: | Rozklady propojovacích sítí na dlouhé cesty |
|---|---|
| Název v anglickém jazyce: | Partitions of interconnection networks into long paths |
| Klíčová slova: | hyperkrychle, augmented cube, hamiltonovské kružnice, vadné hrany |
| Klíčová slova anglicky: | hypercube, augmented cube, hamiltonicity, faulty edges |
| Akademický rok vypsání: | 2011/2012 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ú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í: | 06.10.2011 |
| Datum zadání: | 12.10.2011 |
| Datum potvrzení stud. oddělením: | 06.12.2011 |
| Datum a čas obhajoby: | 18.06.2012 00:00 |
| Datum odevzdání elektronické podoby: | 23.05.2012 |
| Datum odevzdání tištěné podoby: | 24.05.2012 |
| Datum proběhlé obhajoby: | 18.06.2012 |
| Oponenti: | doc. RNDr. Tomáš Dvořák, CSc. |
| Zásady pro vypracování |
| V teorii propojovacích sítí se studují problémy routování pomocí disjunktních cest mezi zadanými dvojicemi či množinami vrcholů. Speciální variantou jsou vrcholově disjunktní cesty, které pokrývají co nejvíce vrcholů. Cílem práce je seznámit se s výsledky v této oblasti a některé jednoduše zobecnit pro více cest, pro slabší typy rozkladů, případně pro další typy propojovacích sítí jako jsou například různé modifikace hyperkrychlí. |
| Seznam odborné literatury |
| F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, California, 1992.
L. H. Hsu and C. K. Lin, Graph theory and interconnection networks, CRC Press, 2008. T. Dvořák and P. Gregor, Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM Journal of Discrete Mathematics, 22(4):1448-1461, 2008. T. Dvořák and P. Gregor, Path partitions of hypercubes, Information Processing Letters, 108(6):402-406, 2008. J.-M. Xu and M. Ma, Survey on path and cycle embedding in some networks, Frontiers of Mathematics in China, 4(2): 217-252, 2008. |