Disertační práce
Získaná ocenění: Cena rektora za vynikající disertační práci Ocenění děkana FI za vynikající disertační práci

Algorithmic Meta-theorems for Restricted Classes of Graphs

RNDr. Jakub Gajarský, učo 172462
Anotace

Algoritmické meta-věty jsou matematická tvrzení typu „Pro všechny problémy vyjádřitelné v dané logice existuje efektivní algoritmus na dané třídě grafů“. Jsou důležitým nástrojem na dokazování existence rychlých algoritmů pro těžké problémy na omezených třídách grafů. V této práci podáváme přehled známých algoritmických meta-vět a dokazujeme několik nových meta-vět. Algoritmické meta-věty se dělí na …více

Abstract

Algorithmic meta-theorems are statements of the form "Every problem expressible in a certain logic is efficiently solvable on a certain class of graphs". They are an important tool for establishing tractability of many important and generally hard problems on restricted classes of graphs. In this work we give an overview of known algorithmic metatheorems together with the techniques used in their proofs …více

Klíčová slova
algoritmické meta-věty parametrizovaná složitost strukturální teorie grafů teorie konečných modelů algorithmic meta-theorems parameterized complexity structural graph theory finite model-theory
Administrativní informace
Práce zkontrolována:
30. 4. 2016 17:44, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
964 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
21. 9. 2016
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponenti

prof. RNDr. Jaroslav Nešetřil, DrSc.
MFF UK v Praze
Prof. Anuj Dawar
University of Cambridge

Konzultant

doc. Mgr. Jan Obdržálek, PhD., učo 1552
ITI FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika (čtyřleté)
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.