基于局部比值法的强弦图带权控制集问题的线性时间算法

摘要：

一个无向图G=(V,E)的顶点子集D(∈)V是控制集,当且仅当任意一个顶点v∈V-D至少与一个顶点u∈D相邻.图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集.结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明.

关键词：局部比值法、强弦图、带权控制集、线性时间算法

所属期刊栏目：44

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金项目61309015;成都学院成都大学模式识别与智能信息处理四川省高校重点实验室开放基金项目,成都大学·龙泉驿区汽车创意设计试点区项目2015-CX00-00010-ZF

在线出版日期：2017-12-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：129-132