ÚVOD / Bakalářské práce / 2018 / Bittnerová Lucie Rút

Ke stažení

Bittnerová Lucie Rút  

Autor
Bittnerová Lucie Rút
Název
Detekce cyklů v dynamických grafech
Rok obhajoby
2018

Anotace

Cílem práce je prozkoumat problém vyhledávání cyklů v dynamickém orientovaném ohodnoceném grafu. Dynamickým grafem budeme v kontextu této práce myslet graf, jehož množina vrcholů se nemění, ale hrany mohou přibývat, ubývat či měnit ohodnocení. Po vyhledání cyklu bude graf modifikován tak, že se najde hrana cyklu s minimálním ohodnocením, tato hrana se z grafu odstraní a ohodnocení ostatních hran cyklu bude sníženo o hodnotu odstraněné hrany. Práce se bude zabývat prozkoumáním v současnosti existujících algoritmů a jejich možnou paralelizací. Součástí bude praktická část, ve které bude porovnána účinnost vyhledávání jednovláknové a paralelní verze vybraných algoritmů.