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

Twin-width of planar graphs

Bc. Jan Jedelský, učo 484988
Anotace

Twin-width je grafový parametr, který v roce 2020 představil Bonnet at al. Neformálně řečeno, twin-width grafu měří jeho podobnost s cografy. Několik \textsf{NP}-těžkých problémů je řešitelných v \textsf{FPT}-čase při parametrizaci pomocí twin-width. Především toto zahrnuje FO-model checking. Většina (pokud ne všechny) těchto algoritmů však předpokládá, že je jim dán svědek omezené twin-width (obvykle …více

Abstract

Twin-width is a graph parameter introduced in 2020 by Bonnet at al. Informally speaking, twin-width of a graph measures its similarity to a cograph. Several \textsf{NP}-hard problems are solvable in \textsf{FPT}-time when parameterized by twin-width. Most notably, this includes first-order model checking. However, most (if not all) of these algorithms assume that a witness of bounded twin-width (usually …více

Klíčová slova
twin-width contraction sequence planar graph
Zadání práce
Twin-width is a new graph parameter (from 2020) which has already attracted a lot of attention, but not much is known about exact values of twin-width of usual graph classes. This work focuses specifically on fine bounds on the twin-width of planar graphs, for which there is a known lower bound of 7, and a stream of upper-bound results recently culminating with the bound of 8 in which the student has participated. The goal of the thesis is to present and possibly further advance this state-of-art knowledge and results. The expected outcomes are in the form of mathematical theorems and proofs.
Administrativní informace
Práce zkontrolována:
25. 12. 2023 08:56, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
782,4 KB / soubor PDF
Přílohy (1)
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

Ander Lamaison Vidarte, PhD
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Principy programovacích jazyků

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.