Bakalářská práce

Twin-width of planar graphs

Dominik Melicher
Anotace

Twin-width je nový grafový atribút prvýkrát zavedený v roku 2020. Je v poslednej dobe intenzívne skúmaný. V tejto práci uvedieme prehľad o twin-width sústredený na posledné pokusy nájsť vrchnú a spodnú hranicu pre rovinné grafy. Následne ukážeme implementácie pre 3 momentálne najlepšie algoritmy na hľadanie kontrakčných sekvencií na rovinných grafoch a porovnáme ich výkony.

Abstract

Twin-width is a new graph attribute introduced in 2020, that is currently being heavily researched. In this thesis, we give an overview of twin-width, focusing on the most recent attempts to find upper and lower bounds for planar graphs. Afterward, we show implementations for the current 3 best algorithms for finding a contraction sequence on planar graphs and compare their performances in practice.

Klíčová slova
twin-width graph theory planar graphs
Zadání práce
The task of this thesis is to give a thorough overview of the very recent (in 2022) rapid development in explicit upper bounds on the twin-width of planar graphs. The student will also implement some of these explicit bounds as practical algorithms for constructing contraction sequences of small red degree. Student may also implement a heuristic algorithm (of his own choice) for the same task. The performance of the implemented algorithms will be compared.
Administrativní informace
Práce zkontrolována:
16. 12. 2022 10:35, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
2,4 MB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
31. 1. 2023
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
Informatika

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.