Bakalářské práce
Parametrizované algoritmy pro problém Min-Power Symmetric Connectivity
Autor
Daniel Dajbov
Rok
2024
Typ
Bakalářská práce
Vedoucí
Mgr. Michal Opler, Ph.D.
Oponenti
doc. RNDr. Dušan Knop, Ph.D.
Katedra
Anotace
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.