Algorithmic aspects of distance constrained labeling: a survey
Algorithmic aspects of distance constrained labeling: a survey
复制标题
DOI：
10.15803/ijnc.4.2_251
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
中科院分区：
文献类型：
--
作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
距离约束的标记问题，例如，L（p，q）-标号和（p，q）-全标号最初是由频率分配激发的。从理论的角度出发，对最小标号的上界和寻找最小标号的时间复杂度进行了深入而广泛的研究。本文从算法的复杂性、可逼近性、精确计算等方面对距离约束标号问题进行了综述。
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.Â