Abstrakt
Je známé, že L(2,1)-Labeling je řešitelný v polynomálním čase pro stromy. V práci ukazujeme, že pro L(2,1,1)-Labeling tomu tak není a rozhodovat L(2,1,1)-Labeling je NP-úplné i pro stromy.
Je známé, že L(2,1)-Labeling je řešitelný v polynomálním čase pro stromy. V práci ukazujeme, že pro L(2,1,1)-Labeling tomu tak není a rozhodovat L(2,1,1)-Labeling je NP-úplné i pro stromy.