| Abstrakt: | V grafe $G=(V,E)$ je množina $V'$ decyklačnou množinou práve vtedy, ak je graf indukovaný množinou vrcholov $V-V'$ acyklický. Problém nájdenia minimálnej decyklačnej množiny je vo všeobecnosti NP-ťažký. Boli však publikované polynomiálne algoritmy na jej nájdenie v špeciálnych triedach grafov, alebo veľmi blízke ohraničenia. V tejto práci navrhneme postup, ktorý určí hornú hranicu mohutnosti decyklačnej množiny pre pancake grafy. Vyčíslime hodnoty získané týmto postupom a porovnáme ich s výsledkami, ktoré dostaneme pomocou greedy algoritmu.
|
|---|