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

Computing twin-width parametrized by restrictive parameters

Bc. Jakub Balabán, učo 485053
Anotace

Twin-width je strukturální grafový parametr představený v roce 2020, který zahrnuje mnoho předtím známých grafových tříd, například rovinné grafy a grafy s omezenou clique-width. Je známo, že FO-model checking je FPT při parametrizaci přes twin-width (pokud je spolu se vstupem poskytnuta odpovídající kontrakční posloupnost). Špatnou zprávou je, že již rozhodování, jestli je twin-width grafu nejvýše …více

Abstract

Twin-width is a structural graph parameter introduced in 2020, which captures many previously known graph classes, such as planar graphs and classes of bounded clique-width. It is known that FO-model checking is FPT when parameterized by twin-width (if a corresponding contraction sequence is given as part of the input). Unfortunately, already deciding whether the twin-width of a graph is at most 4 …více

Klíčová slova
twin-width parameterized complexity feedback edge number kernelization
Zadání práce
Twin-width is a useful graph parameter which is, unfortunately, hard to compute: already deciding whether a graph has twin-width at most 4 is NP-complete. For this reason, it makes sense to consider the problem of computing twin-width parametrized by parameters more restrictive than twin-width itself. The goal of the thesis is to study such restrictive parametrizations, focusing on a parameter called feedback edge number. The expected outcomes are in the form of mathematical theorems and proofs.
Administrativní informace
Práce zkontrolována:
19. 12. 2023 08:30, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
843,3 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
14. 2. 2024
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

RNDr. Filip Pokrývka, Ph.D., učo 433705
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán

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.