Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 368)
Detail práce
   Přihlásit přes CAS
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.
 
Univerzita Karlova | Informační systém UK