Název: Kompaktní I/O-efektivní grafové reprezentace
Překlad názvu: Compact I/O-Efficient Graph Representations
Autoři: Tětek, Jakub ; Gavenčiak, Tomáš (vedoucí práce) ; Mareš, Martin (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2019
Jazyk: eng
Abstrakt: [eng] [cze]
The objective of this thesis is to develop a fast memory-efficient representa- tion of some graphs that occur in real-world applications. We consider separable graph classes (e.g. planar graphs or graphs of bounded genus) and show how to represent them in a way that (1) makes accessing vertices in a walk cache-efficient on average and (2) is highly memory-efficient. In particular, we show a compact representation of separable graph classes with the I/O cost of a random walk of length k being O(K/(Bw)1−c ) w.h.p. In the second part of the thesis, we consider layout of trees with optimal worst-case I/O cost for root-to-leaf traversal, show an additive (+1)-approximation of I/O optimal compact layout and contrast this with a proof of NP-hardness of exact solution. In this thesis, we also prove generalisations of the recursive separator theo- rem. The first one generalises the theorem for weighted graphs and the second one replaces minimum region size by average region size in the bound. 1 Cílem této práce je vyvinout rychlou pamět'ově efektivní reprezentaci někte- rých grafů, které se vyskytují v praktických problémech. Uvažujeme separovatelné třídy grafů (např. rovinné grafy nebo grafy s ome- zeným rodem) a ukazujeme, jak grafy z takových tříd reprezentovat způsobem, který (1) dovoluje v průměru I/O-efektivní přístup k vrcholům při procházce a (2) používá málo paměti. Konkrétně ukazujeme kompaktní reprezentaci grafů ze separovatelných tříd s počtem I/O-přístupů při náhodné procházce délky k rovným O(K/(Bw)1−c ) s vysokou pravděpodobností. V druhé části práce se zabýváme rozložením vrcholů stromu v paměti. Uka- zujeme rozložení, které má optimální počet I/O-přístupů v nejhorším případě při procházení z kořene do listu. Dále ukazujeme aditivní (+1)-aproximaci op- timálního kompaktního rozložení vrcholů a dáváme tento výsledek do kontrastu s důkazem NP-těžkosti přesného řešení. Dále v této práci dokazujeme zobecnění věty o rekurzivních separátorech. První zobecnění rozšiřuje větu pro vážené grafy a druhé zobecnění nahrazuje ve znění věty minimální velikost regionu za průměrnou velikost. 1
Klíčová slova: cache-oblivious algoritmy; kompaktní reprezentace; separovatelné grafy; teorie grafů; cache-oblivious algorithms; compact representation; graph theory; separable graphs

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/108362

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-398637


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce