Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy

• Thesis title in Czech: Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
• Thesis title in English: Hamiltonian cycles in hypercubes with removed vertices
• Key words: hyperkrychle, vadný vrchol, Hamiltonovská laceabilita, izometrický cyklus, izometrický strom
• English key words: hypercube, fault tolerance, Hamiltonian laceability, isometric cycle, isometric tree
• Academic year of topic announcement: 2012/2013
• 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: 24.10.2012
• Date of assignment: 31.10.2012
• Confirmed by Study dept. on: 23.11.2012
• Date and time of defence: 20.06.2013 00:00
• Date of electronic submission: 20.05.2013
• Date of submission of printed version: 21.05.2013
• Date of proceeded defence: 20.06.2013
• Opponents: doc. RNDr. Tomáš Dvořák, CSc.

Guidelines

Využití hyperkrychlí jako propojovacích sítí vede ke studiu jejich robustnosti vzhledem k výskytům chybných vrcholů. Obvyklý počet tolerovatelných chyb je lineární vzhledem k dimenzi hyperkrychle. U hamiltonovských problémů je ale možné dosáhnout exponenciálního počtu, pokud odstraněné vrcholy splňují jisté podmínky na svou vzdálenost. Cílem práce je seznámit se s výsledky v této oblasti a některé snadnější zesílit či zobecnit.

References

F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, California (1992).

P. Gregor and R. Škrekovski, Long cycles in hypercubes with distant faulty vertices, Discrete Mathematics & Theoretical Computer Science 11 (2009), 185-198.

T. Dvořák and P. Gregor. Hamiltonian fault-tolerance of hypercubes, Electronic Notes in Discrete Mathematics 29 (2007), 471-477.