Národní úložiště šedé literatury Nalezeno 2 záznamů.  Hledání trvalo 0.00 vteřin. 
Délkově omezené řezy v grafech
Berg, Michal ; Kolman, Petr (vedoucí práce) ; Dvořák, Pavel (oponent)
V této práci se budeme zabývat problémem délkově omezeného řezu, nazývaného také L-omezený řez. Ukážeme kombinatorický algoritmus pro hledání minimálního L-omezeného řezu na grafech omezené stromové šířky založený na dynamickém programování. Následně také ukážeme, že se tento algoritmus dá použít i pro hledání L-omezeného řezu na rovinných grafech. Také se podíváme na problém (dG(s, t) + 1)-omezeného řezu. Je známé, že tento problém je NP-těžký na obecných grafech. Ale to, jestli je NP-těžký i na rovinných grafech se speciálními vrcholy na vnější stěně, je otevřený problém. Pokusíme se nastínit způsob, kterým bychom možná mohli ukázat, že tento problém je řešitelný v polynomiálním čase.
Aproximace nezávislosti rovinných grafů
Berg, Michal ; Dvořák, Zdeněk (vedoucí práce) ; Fiala, Jiří (oponent)
Problém nezávislé množiny je dobře známý NP-úplný problém, který je NP-úplný i pro rovinné grafy. Ale na rozdíl od obecných grafů, pro rovinné grafy existuje polynomiální aproximační schéma. Popíšeme přesný algoritmus pro hledání největší nezávislé množiny v rovinných grafech založený na dynamickém programování. Tento přesný algoritmus lze jednoduše upravit na polynomiální aproximační schéma. Obě jeho verze jsme implemen- tovali a otestovali. Při tom jsme používali několik generátorů náhodných rovinných grafů. Přesný algoritmus jsme experimentálně srovnávali s dalšími dvěma algoritmy. Aproximační algoritmus jsme srovnávali s jeho přesnou verzí a měřili skutečný aproximační poměr a také jeho časovou náročnost v porovnání s přesnou verzí. Zjistili jsme, že přesný algoritmus na zvolených grafech většinou dokončí výpočet rychleji než ostatní dva algoritmy. Také jsme zjistili, že aproximační verze má vzhledem k teoretickému minimu většinou lepší apro- ximační poměr s dobrou časovou složitostí. 1

Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.