| Riešiteľ: | Stanislav Švec (kontakt: stanislav.svec@student.upjs.sk) |
| Vedúci: | RNDr. Rastislav Krivoš-Belluš, PhD. |
| Ústav: | ÚINF |
| Ciele: | 1. Analyzovať súčasný stav problematiky k-cestného vrcholového pokrytia v rôznych triedach grafov. 2. Vizualizovať existujúce výsledky a algoritmy na rôznych triedach grafov, neváženú ako aj váženú verziu problému k-cestného vrcholového pokrytia. 3. Navrhnúť a implementovať algoritmus na riešenie problému k-cestného vrcholového pokrytia vo vybranej triede grafov a porovnať s existujúcimi výsledkami. |
| Literatúra: | B. Brešar, F. Kardoš, J. Katrenič, G. Semanišin: Minimum k-path vertex cover, December 2010, Discrete Applied Mathematics 159(12), DOI: 10.1016/j.dam.2011.04.008 B. Brešar, R. Krivoš-Belluš, G. Semanišin, P. Šparl: On the weighted k-path vertex cover problem, November 2014, Discrete Applied Mathematics 177:14–18, DOI: 10.1016/j.dam.2014.05.042 Jianhua Tu: A Survey on the k-Path Vertex Cover Problem, January 2022, Axioms 11.191, DOI: 10.3390/axioms11050191 |
Práca sa bude bližšie zaoberať problémom k-cestného vrcholového pokrytia, ktorý som riešil už v bakalárskej práci. Podstatou problému je nájsť v grafe takú množinu vrcholov, že každá cesta danej dĺžky v grafe bude obsahovať aspoň jeden vrchol z danej množiny. Problém je vo všeobecnosti NP-úplný, existujú však možnosti riešiť špecializované prípady tohto problému pomocou efektívnych exaktných aj pravdepodobnostných algoritmov. Takýmito algoritmami sa chceme v práci bližšie zaoberať.