Složitost některých problémů realizovatelnosti pro abstraktní topologické grafy

Abstrakt

Představíme polynomiální algoritmus, který rozhodne, zda daný úplný AT-graf je jednoduše realizovatelný. Na druhou stranu ukážeme, že ostatní podobné realizační problémy pro (úplné) AT-grafy jsou NP-těžké.

Klíčová slova

• complexity
• several
• realizability
• problems
• abstract
• topological
• graphs