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

Parameterized Algorithms on Width Parameters of Graphs

RNDr. Robert Ganian
Anotace

Předmětem práce je aplikování parametrizovaného přístupu k vývoji algoritmů pro různé grafové problémy. Přístup využívá tzv. parametrů k vývoji efektivních algoritmů na velmi obecných třídách grafů. Většina práce se zaměřuje na rankovou šířku jakožto relativně nový strukturální parametr. Ukazujeme, že ranková šířka je velmi užitečným nástrojem k vývoji efektivních algoritmů na obecnější třídě grafů …více

Abstract

The subject of the thesis is the study of the parameterized complexity approach in developing graph algorithms. The approach allows the use of so-called parameters to obtain efficient graph algorithms on a very wide class of graphs. The thesis focuses on providing and proving algorithms for a range of graph problems, giving hardness results and proving various structural and algorithmic properties …více

Klíčová slova
graphs rank-width MSO logic parameterized complexity DAG-width vertex cover twin-cover.
Administrativní informace
Práce zkontrolována:
22. 3. 2012 07:57, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
1,2 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
8. 6. 2012
Práce byla úspěšně obhájena

Vedoucí

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

Oponenti

doc. Mgr. Zdeněk Dvořák, Ph.D.
MFF UK v Praze
Prof. Fedor V. Fomin
University of Bergen
Autor posudku dosud neidentifikován.
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
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Robert Ganian FI D-IN4 IN milta/7
Ganian, R.
19. 1. 2012
Složky
Soubory
Anotace anglicky annotation_english.txt
Ganian, R.
15. 3. 2012
Anotace česky annotation.txt
Ganian, R.
15. 3. 2012
disrg04.pdf
Ganian, R.
19. 1. 2012
Klíčová slova keywords.txt
Ganian, R.
15. 3. 2012
Posudek oponenta dr.Z.Dvorak.pdf
Nazarejová, A.
8. 6. 2012
Posudek oponenta prof.Fomin.pdf
Nazarejová, A.
8. 6. 2012

  • 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.