|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (vedoucí práce) ; Telle, Jan Arne (oponent) ; Obdržálek, Jan (oponent)
Název práce: Parametrizovaná složitost Autor: Ondřej Suchý Katedra (ústav): Katedra aplikované matematiky Školitel: Prof. RNDr. Jan Kratochvíl, CSc. e-mail školitele: honza@kam.mff.cuni.cz Abstrakt: Tato práce se zabývá parametrizovanou složitostí NP-těžkých grafo- vých problémů. Zkoumáme složitost problémů v různých scénářích, vzhle- dem k rozličným parametrům a jejich kombinacím. Naším cílem je spíše rozlišit v tomto mnohorozměrném smyslu, zda daný parametr dělá problém parametrizovaně dostupným, nebo nedostupným, než představit algorit- mus, který dosahuje nejlepší možné časové složitosti. V otázkách, které studujeme, je typicky parametr první volby neúspěšný a tak využíváme méně standardních parametrů. První zkoumaná množina problémů je společným zobecněním mnoha dobře známých a prostudovaných problémů dominance a nezávislosti. Navrhu- jeme zde použít duální parametrizaci a ukážeme, že narozdíl od standardní parametrizace velikostí řešení, tato parametrizace dokáže ohrančit nevyh- nutelnou kombinatorickou explozi. Další studované problémy jsou analogií Steinerova problému v orientovaných grafech. Parametrizace pomocí počtu terminalů se jeví jako dříve neprobádaná alternativa v...
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (vedoucí práce) ; Telle, Jan Arne (oponent) ; Obdržálek, Jan (oponent)
Název práce: Parametrizovaná složitost Autor: Ondřej Suchý Katedra (ústav): Katedra aplikované matematiky Školitel: Prof. RNDr. Jan Kratochvíl, CSc. e-mail školitele: honza@kam.mff.cuni.cz Abstrakt: Tato práce se zabývá parametrizovanou složitostí NP-těžkých grafo- vých problémů. Zkoumáme složitost problémů v různých scénářích, vzhle- dem k rozličným parametrům a jejich kombinacím. Naším cílem je spíše rozlišit v tomto mnohorozměrném smyslu, zda daný parametr dělá problém parametrizovaně dostupným, nebo nedostupným, než představit algorit- mus, který dosahuje nejlepší možné časové složitosti. V otázkách, které studujeme, je typicky parametr první volby neúspěšný a tak využíváme méně standardních parametrů. První zkoumaná množina problémů je společným zobecněním mnoha dobře známých a prostudovaných problémů dominance a nezávislosti. Navrhu- jeme zde použít duální parametrizaci a ukážeme, že narozdíl od standardní parametrizace velikostí řešení, tato parametrizace dokáže ohrančit nevyh- nutelnou kombinatorickou explozi. Další studované problémy jsou analogií Steinerova problému v orientovaných grafech. Parametrizace pomocí počtu terminalů se jeví jako dříve neprobádaná alternativa v...
|
host ::
RSS.