Rigorózní práce

Matroid Algorithms and Their Applications in Optimization

Mgr. Kristýna Pekárková
Anotace

Matroidy jsou kombinatorické struktury, které zobecňují pojmy teorie grafů a lineární algebry. Teorie matroidů má významné uplatnění v oblasti optimalizace; matroidy úzce souvisí s hladovými algoritmy a ukázaly se i jako silný nástroj při návrhu parametrizovaných algoritmů. V této práci se však zaměřujeme na odlišné využití matroidů -- studujeme hloubkové parametry matroidů z jejich algoritmického …více

Abstract

Matroids play an important role in the theory of combinatorial optimization; they have a strong connection to greedy algorithms and have shown to be a powerful tool in the design of parameterized algorithms. However, in this thesis proposal, we aim at using matroids differently: rather than viewing them as an optimization object, we study matroid structural parameters from algorithmic and combinatorial …více

Klíčová slova
matroids combinatorics combinatorial optimization integer programming parameterized complexity fixed-parameter tractability graphs width parameters depth parameters tree-depth branch-depth contraction*-depth
Administrativní informace
Práce zkontrolována:
3. 3. 2023 01:14, prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Plný text práce
1,9 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
1. 6. 2023
Práce byla úspěšně obhájena

Oponenti

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU
doc. Hans Raj Tiwary, M.Sc., Ph.D.
MFF Univerzita Karlova
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Teoretická 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.