Bakalářská práce

Constructive twin-width for posets of small width

Jakub Balabán, učo 485053
Anotace

Twin-width je invariant definován primárně pro grafy, ale rozšířen i na další struktury. Bylo ukázáno, že třídy s malou twin-width mají pěkné vlastnosti, např. se na nich dají efektivně vyhodnocovat prvořádové formule (tzv. FO model checking). Tato práce zkoumá twin-width posetů omezené šířky (což je maximální velikost antiřetězce). Nejprve ukazujeme, že posety šířky 2 mají twin-width nejvýše 2 a že …více

Abstract

Twin-width is an invariant defined primarily for graphs but extended to other structures as well. It has been shown that classes of small twin-width have some nice properties, such as efficient FO model checking. In this thesis, we study the twin-width of posets with bounded width (which is the maximum size of an antichain). First, we show that posets of width 2 have twin-width at most 2 and that this …více

Klíčová slova
poset twin-width contraction poset width chain
Zadání práce
A FOCS2020 paper by Bonnet et al proved that posets of bounded width also have bounded twin-width, in an indirect and rather complicated way. The task is to prove this fact in an elementary direct way, that is, to construct a contraction sequence of bounded error value for such posets. This should be done at least for posets of width two or some other small values, and preferably to outline such a construction for any bound on the width.
Administrativní informace
Práce zkontrolována:
26. 5. 2021 23:13, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
559,2 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
28. 6. 2021
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

Dr. rer. nat. Josef Samuel Mohr
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

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