TY - THES TI - Výpočetní složitost v teorii grafů TT - Computational complexity in graph theory AU - Melka, Jakub AB - In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results AB - V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků. UR - http://hdl.handle.net/20.500.11956/35421 UR - http://www.nusl.cz/ntk/nusl-379578 A2 - Fiala, Jiří A2 - Kratochvíl, Jan LA - cze KW - rekonstrukce grafu KW - hypergraph KW - treewidth KW - hypergraf KW - graph reconstruction KW - Fixed parameter complexity KW - parametrizovaná složitost KW - stromová šírka KW - hvezdné systémy KW - star systems PY - 2011 PB - Univerzita Karlova, Ovocný trh 5, 116 36 Praha 1, http://cuni.cz/ ER -