Genetic Approach To Hypercube Problems
| Thesis title in Czech: | Genetický přístup k problémům na hyperkrychlích |
|---|---|
| Thesis title in English: | Genetic Approach To Hypercube Problems |
| Key words: | hyperkrychle, genetický algoritmus, faktor grafu |
| English key words: | hypercube, genetic algorithm, spanning subgraph |
| Academic year of topic announcement: | 2016/2017 |
| Thesis type: | diploma 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: | 15.02.2017 |
| Date of assignment: | 15.02.2017 |
| Confirmed by Study dept. on: | 06.06.2017 |
| Date and time of defence: | 07.09.2017 09:30 |
| Date of electronic submission: | 21.07.2017 |
| Date of submission of printed version: | 21.07.2017 |
| Date of proceeded defence: | 07.09.2017 |
| Opponents: | doc. Mgr. Martin Pilát, Ph.D. |
| Guidelines |
| 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. |
| References |
| [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. |