Výpočetní složitost problému vzdáleností podmíněného značkování stromů

Abstrakt

V článku jsme potvrdili dlouhodobě otevřenou domněnku, že L(p,q)-značkovací problém je NP-úplný pro stromy jakmile q není dělitelem p.

Klíčová slova

• Computational
• complexity
• distance
• constrained
• labeling
• problem
• trees