Diplomová práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Efficient solvability of graph MSO properties

Bc. Jakub Gajarský, učo 172462
Anotace

V priebehu rokov sa logika MSO ukázala ako vhodný jazyk na vyjadrovanie efektívne riešiteľných vlastností na obmedzených triedach grafov. V tejto práci podávame prehľad tried grafov, pre ktoré existujú efektívne algoritmy na overovanie modelu pre MSO logiku. Prínos práce spočíva v nájdení nového štrukturálneho parametru, ktorý je zúžením clique-width, a pre ktorý existuje rýchlejší algoritmus na overovenie modelu pre MSO logiku.

Abstract

Over the time, MSO graph logic proved to be a suitable language for expressing efficiently solvable properties on restricted classes of graphs. In this work we review some classes of graphs, for which efficient algortithms for MSO model-checking are known. Our contribution consists of finding structural parameter which is a restriction of clique-width, and for which there exists faster MSO model-checking algorithm than the algortihm known for clique-width.

Klíčová slova
monadic second-order logic graph theory parametrized complexity Ehrenfeucht games kernelization
Zadání práce
The subject of this work is to investigate the complexity of the MSO model checking problem on special classes of graphs. Main emphasis is on finding possible new approaches which - on more restricted graphs - result in significantly faster parameterized runtime than the classical MSO2-theorem by Courcelle. The student is expected to review recently published works in this direction, and to come with appropriate extensions and/or new ideas.
Administrativní informace
Práce zkontrolována:
10. 1. 2012 08:26, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
375,3 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
9. 2. 2012
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

RNDr. Robert Ganian, Ph.D.
ext KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
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 Jakub Gajarský FI N-IN TEI, učo 172462 w6sin/6
Gajarský, J.
9. 1. 2012
Složky
Soubory
Anotace anglicky annotation_english.txt
Gajarský, J.
9. 1. 2012
Anotace česky annotation.txt
Gajarský, J.
9. 1. 2012
Klíčová slova keywords.txt
Gajarský, J.
9. 1. 2012
Plný text práce diplomka.pdf
Gajarský, J.
9. 1. 2012
Posudek oponenta dpgajarsky.docx
Ganian, R.
22. 1. 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.