Original title: Genetický přístup k problémům na hyperkrychlích
Translated title: Genetic Approach To Hypercube Problems
Authors: Kuboň, David ; Gregor, Petr (advisor) ; Pilát, Martin (referee)
Document type: Master’s theses
Year: 2017
Language: eng
Abstract: [eng] [cze]
The main focus of this thesis are hypercubes. In the first part, we introduce hypercubes, which form an interesting class of graphs that has practical uses in networks and distributed computing. Because of their varied applications, the thesis describes the graph-theory problems related to hypercubes such as searching for detour spanners, minimizing their maximal degree and finding multiple edge- disjoint spanners. It also overviews current results on selected hypercube problems and proposes a solution using a genetic algorithm. The genetic algorithm is designed, implemented and its performance is evaluated. The conclusion is that applying a genetic algorithm to some hypercube problems is a viable, but not the most effective method. Objektem zájmu práce jsou hyperkrychle. V její první části je představíme coby zajímavou třídu grafů, která má praktické použití v sítích a distribuovaném počítání. Kvůli jejich rozličným aplikacím tato práce popisuje problémy z teorie grafů týkající se hyperkrychlí, jako jsou hledání objížďkových spannerů, minimalizace největšího stuně vrcholu a hledání vícero hranově disjunktních spannerů. Práce též podává přehled aktuálních výsledků pro některé hyperkrychové problémy a navrhuje jejich řešení pomoc genetického algoritmu. Genetický algoritmus je navržem, implementován a jeho výkon je vyhodnocen. Závěrem je, že aplikace genetického algoritmu na některý hyperkrychlový problém je možná, ale nikoli nejeefektivnější metoda.
Keywords: genetic algorithm; hypercube; spanning subgraph; faktor grafu; genetický algoritmus; hyperkrychle

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/90585

Permalink: http://www.nusl.cz/ntk/nusl-365185


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses