Výpočet konvexního obalu grafu

Abstrakt

Dokzajeme NP-těžkost určení nejmenší množiny vrcholů, jejímž konvexním obalem je celý vstupní graf. Dále podáváme polynomiální algoritmus pro případ unit interval grafů, cografů a spli grafů.

Klíčová slova

• computation
• number
• graph