Algoritmy pro průnikové grafy
Algorithms for intersection graphs
diplomová práce (OBHÁJENO)
![Náhled dokumentu](/bitstream/handle/20.500.11956/3293/thumbnail.png?sequence=7&isAllowed=y)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/3293Identifikátory
SIS: 42275
Kolekce
- Kvalifikační práce [10925]
Autor
Vedoucí práce
Oponent práce
Pangrác, Ondřej
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Diskrétní matematika a optimalizace
Katedra / ústav / klinika
Katedra aplikované matematiky
Datum obhajoby
13. 2. 2006
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Čeština
Známka
Velmi dobře
Cílem této práce je předvést techniky řešení problémů hledání maximální nezávislé množiny na průnikových grafech disku v rovině. V průnikovém grafu disku odpovídají vrcholum disky a dva vrcholy jsou sousední, právě když příslušné disky mají neprázdný pruůnik. Hlavní část práce je věnována aproximačním algoritmům a heuristikám (posouvání mřížky, zakázaný podgraf, omezené okolí vrcholu). Podáme přehled tříd diskových grafů (obecné a jednotkové diskové grafy, grafy s omezeným poloměrem disku). Tyto třídy se studují a modelují se na nich praktické problémy. Krátce zmíníme příklady možného praktického využití (značkování map, facility placement). Součástí práce je program, který demonstruje vybrané algoritmy a heuristiky.
The goal of this thesis is to show techniques of solving the maximum independent set problem on intersection graphs of disks in the plane. An intersection graph is a graph whose vertices are represented by disks and two vertices are adjacent if and only if the corresponding disks have non-empty intersection. The main section of the paper is dedicated to the approximation algorithms and heuristics (grid shifting, forbidden subgraph, bounded neighborhood of a vertex). We will give an overview of disk graph classes (general and unit disk graphs, graphs with bounded radius of disks). These classes are studied and used to model practical problems. We will briefly describe some of these applications (map labelling, facility placement). A program demonstrating several algorithms and heuristics is enclosed with this work.