Bakalářská práce

Tree-depth of grids

Štěpán Mikéska
Anotace

Stromová hloubka je grafový parametr, který měří, jak blízko má graf ke hvězdě. U grafů s malou stromovou hloubkou se mnoho NP-těžkých problémů stává zvládnutelnými; samotný výpočet stromové hloubky je však NP-těžký problém a její přesné hodnoty jsou známy pouze pro velmi omezené třídy grafů. V této práci se zabýváme teorii stromové hloubky, eliminačních stromů a separátorů a tuto teorii využíváme …více

Abstract

Tree-depth is a graph parameter that measures how close a graph is to a star. For graphs with small tree-depth, many NP-hard problems become tractable; however, calculating tree-depth is itself an NP-hard problem, and exact tree-depth values are known only for very restricted classes of graphs. In this thesis, we develop the theory of tree-depth, elimination trees, and separators, and use this theory …více

Klíčová slova
graph tree-depth vertex ranking centered coloring grid graph dynamic programming
Zadání práce
Tree-depth is one of the most useful structural graph parameters. In contrast to the related parameters tree-width and clique-width, the exact tree-depth of two-dimensional grid graphs is unknown. The student will survey known results about the tree-depth of n * m grids and try to prove new statements, focusing on the case in which n is much smaller than m.
Administrativní informace
Práce zkontrolována:
22. 5. 2026 11:11, RNDr. Jakub Balabán, učo 485053
Plný text práce
563,7 KB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
26. 6. 2026
Práce byla úspěšně obhájena

Vedoucí

RNDr. Jakub Balabán, učo 485053
KTP FI MU

Oponent

RNDr. Jakub Gajarský, Ph.D., učo 172462
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.