摘要
图G的一个点集S是[1,2]-集,若每个不在S中的点至少与S中的1个点相邻且至多与S中的2个点相邻.一个图的所有[1,2]-集中元素个数最小的集合,其元素个数称为图的[1,2]-数.针对树的[1,2]-数的计算问题进行研究.首先,根据[1,2]-数的定义给出了一个0-1规划模型,求解这个0-1规划可以得到图的[1,2]-数的精确值.然后,基于贪婪策略将树进行星分解,给出计算[1,2]-数的两个近似算法.最后,分析了两个近似算法的计算复杂度和性能.
A vertex set S of a graph G is a [1,2]-set. Every vertex which is not in S satisfies that it is adjacent to at least one vertex, but not more than two vertices in S. The [1,2]-number equals the minimum cardinality of a [1,2]-set in G. The algorithms of calculating the [1,2]-number of trees were studied. Firstly, a 0-1 programming model was constructed according to the definition of the [1,2]-number. The exact [1,2]-number of the tree was got by solving the 0-1 programming model. Through star-decomposition of the tree based on the greedy strategy, two approximate algorithms, which calculated the [1,2]-number of trees, were got. Finally, the computing complexity and the performances of the two approximate algorithms were analyzed.
出处
《中国计量学院学报》
2015年第2期243-246,共4页
Journal of China Jiliang University
基金
国家自然科学基金面上项目(No.61173002)
关键词
[1
2]-数
0-1规划
贪婪策略
近似算法
[1,2]--number
0-1 programming
greedy strategy
approximate algorithm
