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

Stack number and queue number of graphs

Adam Straka, učo 493034
Anotace

V tejto práci uvádzame prehľad grafových invariantov queue number a stack number, tiež nazývaného page number alebo book thickness. Kvôli ich podobnosti je už dlho študovaná ich vzájomná závislosť. Dnes už je známe, že stack number nie je z hora ohraničený invariantom queue number. V našej práci uvádzame zjednodušený dôkaz tohto výsledku. Tiež sa venujeme známym výsledkom o hornom ohraničení queue number invariantom stack number.

Abstract

In this thesis, we give an overview of graph invariants queue number and stack number, the latter also called page number or book thickness. Due to their similarity, it has been studied for a long time, whether one is bounded by the other. It is now known that stack number is not bounded by queue number. We present a simplified proof of this result. We also study the known results about the stack number bound on the queue number.

Klíčová slova
stack number page number book thickness queue number
Zadání práce
The student will give an overview of the stack and queue numbers of graphs, and of what is known about their mutual relation. Then he will give a simplified proof of the known fact that the stack-number of a graph is, in general, not bounded by its queue-number.
Administrativní informace
Práce zkontrolována:
16. 12. 2022 10:46, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
699,6 KB / soubor PDF
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

doc. Mgr. Jan Obdržálek, PhD., učo 1552
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.

  • 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.