Název: Parametrizovaná složitost v teorii grafů
Překlad názvu: Paramterized complexity in graph theory
Autoři: Suchý, Ondřej ; Kráľ, Daniel (oponent) ; Kratochvíl, Jan (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2006
Jazyk: cze
Abstrakt: [cze] [eng]
Seidelovo přepnutí množiny vrcholu je operace, která z grafu odebere hrany vycházející z této množiny a přidá do něj hrany tam, kde mezi množinou a zbytkem grafu nebyly. Ostatní hrany nejsou touto operací dotčeny. Parametrizovaná složitost se ptá, zda lze exponenciální část algoritmu pro těžké problémy omezit nějakou funkcí pouze zvoleného parametru, u nejž lze očekávat malé hodnoty. Tato práce zkoumá složitost otázek, zda lze zadaný graf převést na graf s nějakou vlastností P pomocí Seidelova přepnutí, z parametrizovaného hlediska. Nejdříve krátce shrneme dosud známé výsledky. Pak předvedeme parametrizovanou dostupnost přepnutí na regulární grafy, grafy s omezeným stupněm vrcholu, s omezeným počtem hran a grafy prosté zakázaného podgrafu. Krátce podáme základní definice a postupy parametrizované složitosti. Seidel's switching of a set of vertices of a graph is an operation which deletes the edges leaving this set from the graph and adds those edges between the set and the rest of graph that weren't in the original graph. Other edges remain untouched by this operation. Parameterized complexity asks if the exponential part of algorithms for hard problems can be bounded by some function only of selected parameters, which we assume small. In this thesis, we study the complexity of a question if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized point of view. First we give an overview of known results. Then we show fixed-parameter tractability of switching to a regular graph, a graph with bounded degree of vertices, bounded number of edges and a graph without a forbidden subgraph. We briefly introduce basic definitions and techniques of parameterized complexity.

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

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


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