Hamiltonicity of hypercubes without k-snakes and k-coils
| Název práce v češtině: | Hamiltonovskost hyperkrychlí bez k-hadů a k-cívek |
|---|---|
| Název v anglickém jazyce: | Hamiltonicity of hypercubes without k-snakes and k-coils |
| Klíčová slova: | hyperkrychle, vadný vrchol, Hamiltonovskost, k-had, k-cívka |
| Klíčová slova anglicky: | hypercube, faulty vertex, Hamiltonicity, k-snake, k-coil |
| Akademický rok vypsání: | 2014/2015 |
| Typ práce: | diplomová 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í: | 10.04.2015 |
| Datum zadání: | 10.04.2015 |
| Datum potvrzení stud. oddělením: | 07.07.2015 |
| Datum a čas obhajoby: | 20.06.2016 09:00 |
| Datum odevzdání elektronické podoby: | 11.05.2016 |
| Datum odevzdání tištěné podoby: | 11.05.2016 |
| Datum proběhlé obhajoby: | 20.06.2016 |
| Oponenti: | RNDr. Jiří Fink, Ph.D. |
| Zásady pro vypracování |
| A snake (coil) is an induced path (cycle) in a hypercube. It has received attention in a well known problem called snake-in-the-box (coil-in-the-box) which asks for a longest snake (coil) in a hypercube. Both snakes and coils have been generalized to k-snakes and k-coils with parameter k which is referred to as a spread. The goal of this thesis is to familiarize with k-snakes and k-coils and to explore whether they could be avoided by a Hamiltonian path or a Hamiltonian cycle for some k. The thesis will also introduce and study a dragon which is an induced tree in a hypercube and its generalization to a k-dragon. |
| Seznam odborné literatury |
| S. Hood, D. Recoskie, J. Sawada, D. Wong, Snakes, coils, and single-track circuit codes with spread k, Journal of Combinatorial Optimization (2013), 1-21.
R. Singleton, Generalized Snake-in-the-Box Codes, Electronic Computers, IEEE Transactions on Electronic Computers (1966), 596-602. Chao-Ming Sun and Yue-Dar Jou, Hamiltonian laceability of hypercubes with some faulty elements, Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, ICNSC (2009), 626-630. 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. |