Mgr. Michal Opler, Ph.D.

V poslední době začínáme lépe rozumět vztahu mezi strukturálními vlastnostmi grafů a složitostí grafových problémů. Jako příklad lze uvést efektivnější algoritmy pro řadu úloh na rovinných grafech či grafech s omezenou stromovou šířkou. Cílem práce je zkoumat, jak lze podobné strukturální vlastnosti využít při návrhu efektivních algoritmů, případně k dokázání jejich neexistence za standardních složitostních předpokladů. Uvažované problémy mohou sahat od klasických grafových úloh, jako jsou různé varianty barvení, až po prakticky motivované problémy, například multiagentní plánování nebo návrh dopravních sítí.

Cílem práce je zkoumat strukturální vlastnosti dědičných tříd permutací a jejich využití při analýze složitosti algoritmických problémů a enumeraci. Jedním z předpokládaných nástrojů je konečná teorie modelů, zejména prostřednictvím monadické logiky druhého řádu a interpretací — přístup, který v poslední době vedl k řadě významných výsledků v teorii grafů.

Mgr. Michal Opler, Ph.D.

doc. RNDr. Dušan Knop, Ph.D.

Katedra teoretické informatiky

V bakalářské práci představíme problém Min Power Symmetric connectivity (MinPSC), který je na obecných grafech NP-těžký. Problém MinPSC má uplatněni v sítích, kde pro daný uzel chceme zmenšit jeho spotřebu energii na co nejmenší úroveň a požadujeme přitom, aby každý uzel mohl komunikovat s ostatními. V této práci zkoumáme problém MinPSC ze pohledu dvou strukturálních parametru. A to z vrcholového pokrytí a sousedské různorodosti.

Práce na DSpace