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. 1Cí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