Rigorózní práce

Parameterized Algorithms for Computing Twin-Width

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

Twin-width je strukturální grafový parametr zavedený v roce 2020, který zachycuje mnoho dříve známých tříd grafů, jako jsou například rovinné grafy a třídy s omezenou clique-width. Je známo, že FO-model checking je FPT při parametrizaci pomocí twin-width (pokud je součástí vstupu také odpovídající kontrakční posloupnost). Bohužel, již rozhodnout, zda má graf twin-width nejvýše 4, je NP-úplný problém …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 fixed-parameter algorithms vertex integrity feedback edge number
Administrativní informace
Práce zkontrolována:
2. 9. 2025 20:21, 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
19. 1. 2026
Práce byla úspěšně obhájena

Oponenti

Mgr. Marek Filakovský, Ph.D., učo 211334
KTP FI MU
RNDr. Tomáš Masařík, Ph.D.
MIM University of Warsaw
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Teoretická informatika

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

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

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