Hlavní stránka > Výsledky hledání: Tětek, Jakub
Hledej:
Tipy pro vyhledávaní :: Rozšířené hledání
Hledej ve sbírkách:
Seřadit podle: Zobrazit výsledky: Výstupní formát:
Národní úložiště šedé literatury Nalezeno 1 záznamů.  Hledání trvalo 0.00 vteřin. 
Compact I/O-Efficient Graph Representations
 Tětek, Jakub ; Gavenčiak, Tomáš (vedoucí práce) ; Mareš, Martin (oponent)
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
Úplný záznam

Viz též: podobná jména autorů
1 Tětek, Jan
2 Tětek, Josef
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.
Digitální repozitář :: Hledej :: Nový záznam :: Personalizace :: Nápověda
Powered by Invenio v1.1.2
Spravuje admin.invenio@techlib.cz
Tato stránka je dostupná také v následujících jazycích:
Česky  English