Diplomová práce

Complexity and FPT algorithms for stack, queue and track numbers

Bc. Adam Straka, učo 493034
Anotace

V tejto práci študujeme zložitosť algoritmických problémov týkajúcich sa grafových invariantov stack, queue a track number. Je známe, že veľa problémov, s ktorými sa človek stretne pri práci s týmito invariantami je NP-úplných. Pri takýchto problémoch študujeme ich parametrizovanú zložitosť. Táto oblasť je extenzívne preskúmaná. Hlavné nástroje, ktoré sa v tejto oblasti využívajú, sú dynamické programovanie …více

Abstract

We study the complexity of several algorithmic problems regarding the stack, queue and track number of graphs. Many of the problems which arise while working with these parameters are known to be NP-complete. For such problems, we study their parameterized complexity. This area is quite extensively researched. The main tools that are being used are dynamic programming and kernelization. We describe …více

Klíčová slova
stack number queue number track number complexity parameterized complexity
Zadání práce
The student will survey existing literature and results on the computational complexity of the problems to determine the stack, queue and track number of graphs. The goal is to provide a unifying comprehensive picture of the complexity of the three related problems on common graph classes, and to try to fill missing pieces in this picture.
Administrativní informace
Práce zkontrolována:
23. 5. 2025 12:15, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
546,1 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
19. 6. 2025
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

RNDr. Jan Jedelský, učo 484988
KTP FI MU

Konzultant

RNDr. Jakub Balabán, učo 485053
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Diskrétní algoritmy a modely

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.