Algorithmic aspects of distance constrained labeling: a survey

Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno


Distance constrained labeling problems, e.g., L(p,q)-labeling and (p,q)-total labeling, are originally motivated by the frequency assignment. From the viewpoint of theory, the upper bounds on the labeling numbers and the time complexity of finding a minimum labeling are intensively and extensively studied. In this paper, we survey the distance constrained labeling problems from algorithmic aspects, that is, computational complexity, approximability, exact computation, and so on. 


distance constrained labeling; L(2, 1)-labeling; (2, 1)-total labeling; frequency assignment

Full Text:



  • There are currently no refbacks.