Rozklady propojovacích sítí na dlouhé cesty
| Thesis title in Czech: | Rozklady propojovacích sítí na dlouhé cesty |
|---|---|
| Thesis title in English: | Partitions of interconnection networks into long paths |
| Key words: | hyperkrychle, augmented cube, hamiltonovské kružnice, vadné hrany |
| English key words: | hypercube, augmented cube, hamiltonicity, faulty edges |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| 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: | 06.10.2011 |
| Date of assignment: | 12.10.2011 |
| Confirmed by Study dept. on: | 06.12.2011 |
| Date and time of defence: | 18.06.2012 00:00 |
| Date of electronic submission: | 23.05.2012 |
| Date of submission of printed version: | 24.05.2012 |
| Date of proceeded defence: | 18.06.2012 |
| Opponents: | doc. RNDr. Tomáš Dvořák, CSc. |
| Guidelines |
| 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í. |
| References |
| 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. |