| 基于局部比值法的强弦图带权控制集问题的线性时间算法 |
| |
| 引用本文： | 张修军,吴璞,杨洪,邵泽辉.基于局部比值法的强弦图带权控制集问题的线性时间算法[J].计算机科学,2017,44(Z6):129-132. |
| |
| 作者姓名： | 张修军 吴璞 杨洪 邵泽辉 |
| |
| 作者单位： | 成都学院成都大学信息科学与工程学院 成都610106;成都学院成都大学模式识别与智能信息处理四川省高校重点实验室 成都610106,成都学院成都大学信息科学与工程学院 成都610106,成都学院成都大学信息科学与工程学院 成都610106;成都学院成都大学模式识别与智能信息处理四川省高校重点实验室 成都610106,成都学院成都大学信息科学与工程学院 成都610106;成都学院成都大学模式识别与智能信息处理四川省高校重点实验室 成都610106 |
| |
| 基金项目： | 本文受国家自然科学基金项目(61309015),成都学院(成都大学)模式识别与智能信息处理四川省高校重点实验室开放基金项目,成都大学·龙泉驿区汽车创意设计试点区项目(2015-CX00-00010-ZF)资助 |
| |
| 摘 要： | 一个无向图G＝(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V－D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。
|
| 关 键 词： | 局部比值法 强弦图 带权控制集 线性时间算法 |
Linear-time Algorithm for Weighted Domination Problem of Strongly Chordal Graph Based on Local Ratio Method |
| |
| ZHANG Xiu-jun,WU Pu,YANG Hong and SHAO Ze-hui.Linear-time Algorithm for Weighted Domination Problem of Strongly Chordal Graph Based on Local Ratio Method[J].Computer Science,2017,44(Z6):129-132. |
| |
| Authors: | ZHANG Xiu-jun WU Pu YANG Hong and SHAO Ze-hui |
| |
| Affiliation: | School of Information Science and Engineering,Chengdu University,Chengdu 610106,China;Key Laboratory of Pattern Recognition and Intelligent Information Processing,Institutions of Higher Education of Sichuan Province,Chengdu University,Chengdu 610106,China,School of Information Science and Engineering,Chengdu University,Chengdu 610106,China,School of Information Science and Engineering,Chengdu University,Chengdu 610106,China;Key Laboratory of Pattern Recognition and Intelligent Information Processing,Institutions of Higher Education of Sichuan Province,Chengdu University,Chengdu 610106,China and School of Information Science and Engineering,Chengdu University,Chengdu 610106,China;Key Laboratory of Pattern Recognition and Intelligent Information Processing,Institutions of Higher Education of Sichuan Province,Chengdu University,Chengdu 610106,China |
| |
| Abstract: | |
| |
| Keywords: | Local ratio method Strongly chordal graph Weighted dominating set Linear time algorithm |
|
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
|
