Computational complexity of the distance constrained labeling problem for trees

Abstract

In the paper we solve long-lasting conjecture by showing that the L(p,q) labeling problem for trees is NP-complete whenever q is not a divisor of p.

Keywords

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