Bakalářská práce

Classes of bounded and unbounded twin-width

Jan Jedelský, učo 484988
Anotace

V této práci vytvoříme shrnutí twin-width se zaměřením na kritéria pro určení, zda-li má daná třída grafů shora omezenou twin-width. Dále shrneme třídy grafů, u nichž je známo, zda je jejich twin-width omezená či nikoliv. Poté studujeme twin-width průnikových grafů a ukážeme, že třída vlastních průnikových grafů cest ve stromech a třída vlastních H-grafů, kde H není cyklus ani cesta, nemají shora …více

Abstract

In this thesis, we give an overview of twin-width, focusing on criteria for determining whenever a class of graphs has bounded twin-width. Furthermore, we summarize known classes of graphs with bounded and unbounded twin-width. Afterward, we study the twin-width of intersection graphs and show that the class of proper intersection graphs of paths in trees and the class of proper H-graphs …více

Klíčová slova
twin-width intersection graph H-graphs graph theory graph
Zadání práce
The student shall give a thorough overview of the new notion of twin-width (from a FOCS2020 paper by Bonnet et al.); focusing especially on a summary of known structural and counting criteria for determining whether a prescribed graph class is of bounded or unbounded twin-width. Then he will use these criteria to discuss boundedness of twin-width for several particular, (usually) geometrically defined graph classes.
Administrativní informace
Práce zkontrolována:
26. 5. 2021 23:11, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
817,3 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

Frederik Garbe, PhD
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.