Bakalářská práce

Parametrizované algoritmy pro grafy s omezenou modulární šířkou

Parameterized algorithms for modular-width

Michal Románek
Anotace

Táto práca sa zaoberá zložitosťou niektorých výpočetne náročných problémov na grafoch s obmedzenou "neighborhood diversity" a modulárnou šírkou. Nachádza sa v nej krátky súhrn súčasného stavu riešenej problematiky a často používaných techník riešenia problémov na grafoch s obmedzenou "neighborhood diversity". Následne sú tieto techniky aplikované na vytvorenie vlastných algoritmov na riešenie problémov …více

Abstract

This thesis is dealing with the complexity of some hard problems on graphs bounded by neighborhood diversity and modular-width. We provide a short overview of the current state of art and commonly used techniques for solving problems on graphs bounded by neighborhood diversity. Then we apply these and come up with original algorithms for problems on graphs bounded by modular-width, namely the independent …více

Klíčová slova
parameterized complexity neighborhood diversity modular-width edge dominating set dominating set independent set
Zadání práce
Student se bude zabývat návrhem efektivních algoritmů pro třídy grafů s omezenou modulární šířkou. Student podá stručný přehled stávajících algoritmických výsledků pro modulární šířku a nastuduje techniky návrhů algoritmů pro třídy grafů s omezenou "neighborhood diversity" (podobný, ale jednodušší pojem než modulární šířka). Ty se pak pokusí uplatnit a případně rozšířít na grafy s omezenou modulární šířkou. Očekávaným výsledkem práce jsou parametrizované algoritmy pro klasické problémy jako nalezení minimální dominující nebo nezávislé množiny v grafech s omezenou modulární šířkou, případně pro složitější problémy nové algoritmy pro grafy s omezenou "neighborhood diversity".
Administrativní informace
Práce zkontrolována:
24. 5. 2016 01:05, RNDr. Jakub Gajarský, Ph.D., učo 172462
Plný text práce
1,1 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
24. 6. 2016
Práce byla úspěšně obhájena

Vedoucí

RNDr. Jakub Gajarský, Ph.D., učo 172462
ITI FI MU

Oponent

doc. Mgr. Jan Obdržálek, PhD., učo 1552
ITI FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná 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.