摘要
一个无向图G=(V,E)的顶点子集D■V是控制集,当且仅当任意一个顶点v∈V-D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。
In an undirected graph G=(V,E),D■Vis dominating set if and only if any vertex v∈V-Dadjacent to at least one vertex u∈D.The minimum weight dominating set problem consists of finding a dominating set of a graph G with minimum weight.By applying with the properties of strongly chordal graph,a linear-time algorithm based on local ratio method for the minimum weight dominating set problem on strongly chordal graph was proposed.We also provided the proof of the time complexity of the proposed algorithm.
出处
《计算机科学》
CSCD
北大核心
2017年第S1期129-132,共4页
Computer Science
基金
国家自然科学基金项目(61309015)
成都学院(成都大学)模式识别与智能信息处理四川省高校重点实验室开放基金项目
成都大学.龙泉驿区汽车创意设计试点区项目(2015-CX00-00010-ZF)资助
关键词
局部比值法
强弦图
带权控制集
线性时间算法
Local ratio method
Strongly chordal graph
Weighted dominating set
Linear time algorithm
