Genetic Approach To Hypercube Problems

• Název práce v češtině: Genetický přístup k problémům na hyperkrychlích
• Název v anglickém jazyce: Genetic Approach To Hypercube Problems
• Klíčová slova: hyperkrychle, genetický algoritmus, faktor grafu
• Klíčová slova anglicky: hypercube, genetic algorithm, spanning subgraph
• Akademický rok vypsání: 2016/2017
• 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í: 15.02.2017
• Datum zadání: 15.02.2017
• Datum potvrzení stud. oddělením: 06.06.2017
• Datum a čas obhajoby: 07.09.2017 09:30
• Datum odevzdání elektronické podoby: 21.07.2017
• Datum odevzdání tištěné podoby: 21.07.2017
• Datum proběhlé obhajoby: 07.09.2017
• Oponenti: doc. Mgr. Martin Pilát, Ph.D.

Zásady pro vypracování

The n-dimensional hypercube Qn is an undirected graph on vertices {0,1}^n with edges between all pairs of vertices having Hamming distance equal to one. A (k,t)-detour subgraph of a graph G is a spanning subgraph H such that for any two vertices with distance at most t in G, their distance in H is increased at most by k.

Some common problems related to hypercubes include finding a subgraph that has a particular property, for example being a (1,3)-detour subgraph with minimal number of edges and/or low maximal degree or finding multiple edge-disjoint spanners. There are known results for all the mentioned problems that were achieved using traditional graph-theory methods.

The goal of this thesis is to present an overview of current results achieved by traditional methods, and to examine the possibility to solve some of these problems for low dimensions by means of genetic algorithms. This task includes design, implementation and evaluation of the specific genetic algorithm.

Seznam odborné literatury

[1] Peter Hamburger, Alexandr V Kostochka, and Alexander Sidorenko. Hypercube subgraphs with local detours. Journal of Graph Theory, 30(2):101-111, 1999.

[2] Melanie Mitchell. An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, USA, 1996.