Název: Řídké třídy grafů
Překlad názvu: Nowhere-dense classes of graphs
Autoři: Tůma, Vojtěch ; Dvořák, Zdeněk (vedoucí práce) ; Mareš, Martin (oponent)
Typ dokumentu: Diplomové práce
Rok: 2013
Jazyk: eng
Abstrakt: [eng] [cze]
In this thesis we study sparse classes of graphs and their properties usable for design of algorithms and data structures. Our specific focus is on the con- cepts of bounded expansion and tree-depth, developed in recent years mainly by J. Nešetřil and P. Ossona de Mendez. We first give a brief introduction to the theory as whole and survey tools and results from related areas of parametrised complexity and algorithmic model theory. The main part of the thesis, application of the theory, presents two new dynamic data structures. The first is for keeping a tree-depth decomposition of a graph, the second counts appearances of fixed subgraphs in a given graph. The time and space complexity of operations of both structures is guaranteed to be low when used for sparse graphs. 1 V této práci se zabýváme řídkými třídami grafů a jejich vlastnostmi využitelnými pro návrh algoritmů a datových struktur. Speciálně se zaměřujeme na nedávno zavedené koncepty omezené expanse a stromové hloubky, které zavedli J. Nešetřil a P. Ossona de Mendez. V této práci nejprve podáme stručný úvod do prob- lematiky a shrneme důležité výsledky a nástroje z parametrisované složitosti a algoritmické teorie modelů. Hlavní část této práce, aplikace teoretických poznatků, přináší dva nové výsledky z oblasti dynamických datových struktur. První slouží k udržování dekomposice grafu s omezenou stromovou hloubkou, druhá počítá výskyty zadaného podgrafu v udržovaném grafu. Časová i prostorová složitost operací obou struk- tur je při použití na řídké třídy grafů nízká. 1
Klíčová slova: algoritmické metavěty; dynamické datové struktury; teorie řídkých grafů; algorithmic metatheorems; dynamic data structures; sparse graph theory

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/52064

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


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 > Diplomové práce