一个新的极大独立集算法及独立数的界

doi:10.3778/j.issn.1002-8331.2008.26.014

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (26): 48-50.DOI: 10.3778/j.issn.1002-8331.2008.26.014

一个新的极大独立集算法及独立数的界

李勤丰¹,李尤丰²,丁根宏³

1.金陵科技学院基础部，南京 210001
2.金陵科技学院信息技术学院，南京 210001
3.河海大学理学院，南京 210098

收稿日期:2007-11-06 修回日期:2008-02-18 出版日期:2008-09-11 发布日期:2008-09-11
通讯作者: 李勤丰

New algorithm of maximal independent set and upper bound of independent number

LI Qin-feng¹,LI You-feng²,DING Gen-hong³

1.Department of Foundation Courses，Jinling Institute of Technology，Nanjing 210001，China
2.School of Computer and Information Technology，Jinling Institute of Technology，Nanjing 210001，China
3.College of Science，Hohai University，Nanjing 210098，China

Received:2007-11-06 Revised:2008-02-18 Online:2008-09-11 Published:2008-09-11
Contact: LI Qin-feng

摘要/Abstract

摘要： 最大独立集问题是图论中典型的组合优化问题，有着广泛的实际应用价值。分析了现有独立数的界公式后给出了新的上界公式，并通过分析贪婪算法和独立集自身的特征，给出了新的求解极大独立集的算法，并证明了其确定性。然后用实例验证了该算法的有效性。

关键词: 极大独立集, 界, 贪婪算法, 图论

Abstract: The maximum independent set problem is a classical problem in combinatorial optimization.It has been used widely.Firstly an upper bound is shown.Then by the analysis of the character of the maximum independent sets and the colligation of meta-heuristic algorithm，a new algorithm is given and its assurance is proved.After abundant experiments，the results show adequately that the algorithm presented in the thesis is efficacious.

Key words: maximal independent set, bound, greedy algorithm, graph theory

李勤丰¹,李尤丰²,丁根宏³. 一个新的极大独立集算法及独立数的界[J]. 计算机工程与应用, 2008, 44(26): 48-50.

LI Qin-feng¹,LI You-feng²,DING Gen-hong³. New algorithm of maximal independent set and upper bound of independent number[J]. Computer Engineering and Applications, 2008, 44(26): 48-50.

[1]	程帅，吴华锋，梅骁峻. 交替非负约束框架的海洋传感网协同定位[J]. 计算机工程与应用, 2021, 57(23): 129-136.
[2]	马成齐，李学华，张兰杰，向维. 抗遮挡的单目深度估计算法[J]. 计算机工程与应用, 2021, 57(2): 217-222.
[3]	乔勋双，毕文杰. 考虑时变奖励的多摇臂算法在动态定价中的应用[J]. 计算机工程与应用, 2021, 57(12): 237-242.
[4]	方承志，火兴龙，程宥铖. 联合边界框校准的自然场景文本检测[J]. 计算机工程与应用, 2021, 57(1): 161-167.
[5]	魏锋涛，史云鹏，石坤. 具有组合变异策略的回溯搜索优化算法[J]. 计算机工程与应用, 2020, 56(9): 41-47.
[6]	朱明，赵兴运. 分区最大化色域边界描述器的空区插值算法[J]. 计算机工程与应用, 2020, 56(8): 192-198.
[7]	冯学钢，周大可，杨欣. 结合掩膜机制的间隔最大化相关滤波跟踪算法[J]. 计算机工程与应用, 2020, 56(6): 153-158.
[8]	冯纾，王军锋，蔡勇，冯登明，王文军. 低光照度下人机界面背景色眼动分析评价研究[J]. 计算机工程与应用, 2020, 56(4): 262-267.
[9]	苟海雯，宁爱兵，胡沁，张惠珍. 带惩罚的无容量设施选址问题的降阶回溯算法[J]. 计算机工程与应用, 2020, 56(24): 43-49.
[10]	王南，许道云. 针对弱边缘信息的左心室图像分割算法[J]. 计算机工程与应用, 2020, 56(23): 211-219.
[11]	谭正华，戴立平，文阳，李国泰. 基于约简属性和阈值分割的决策树构建方法[J]. 计算机工程与应用, 2020, 56(22): 160-165.
[12]	徐娟，姚如贵，高岩，朱礼亚. 信道估计误差有界时速率损失上界统计特性[J]. 计算机工程与应用, 2020, 56(20): 82-86.
[13]	韩素青，成慧雯，王宝丽. 三支决策朴素贝叶斯增量学习算法研究[J]. 计算机工程与应用, 2020, 56(18): 42-49.
[14]	郝宇辰，刘臣. 媒体干预及用户信任的网络社区观点演化研究[J]. 计算机工程与应用, 2020, 56(16): 156-164.
[15]	孟东霞，李玉鑑. 融合特征边界信息的不平衡数据过采样方法[J]. 计算机工程与应用, 2020, 56(14): 156-160.

一个新的极大独立集算法及独立数的界

New algorithm of maximal independent set and upper bound of independent number

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics