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

doi:10.3778/j.issn.1002-8331.2008.26.014

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (26): 48-50.DOI: 10.3778/j.issn.1002-8331.2008.26.014

• 理论研究 • Previous Articles Next Articles

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

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

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

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

通讯作者: 李勤丰

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

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

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

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.

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

[1]	CHENG Shuai, WU Huafeng, MEI Xiaojun. Alternative Nonnegative Constrained Framework-Based Cooperative Localization Algorithm in Ocean Sensor Networks [J]. Computer Engineering and Applications, 2021, 57(23): 129-136.
[2]	ZHANG Cuiwen, ZHANG Changlun, HE Qiang, WANG Hengyou. Research on Loss Function of Box Regression in Object Detection [J]. Computer Engineering and Applications, 2021, 57(20): 97-103.
[3]	MA Chengqi, LI Xuehua, ZHANG Lanjie, XIANG Wei. Anti-oclusion Monocular Depth Estimation Algorithm [J]. Computer Engineering and Applications, 2021, 57(2): 217-222.
[4]	LI Wei, DAI Zhaoxia, ZHANG Xiangdong, ZHANG Liang, SHEN Peiyi. Application of Rotating Target Detection Algorithm in Satellite Image [J]. Computer Engineering and Applications, 2021, 57(16): 134-141.
[5]	JIANG Liangzhong, LEI Hang, LI Zhenhao, QIAN Weizhong, SHI Gantu. Research on Outbound Slotting Optimization Method by Using Adaptive Optimization Weights [J]. Computer Engineering and Applications, 2021, 57(15): 271-278.
[6]	QIAO Xunshuang, BI Wenjie. Application of Multi-armed Bandit Algorithm with Time-Varying Rewardsin Dynamic Pricing [J]. Computer Engineering and Applications, 2021, 57(12): 237-242.
[7]	XU Jingzhong, MA Lina. Automatic Boundary Extraction from Building Point Clouds Based on Virtual Grids [J]. Computer Engineering and Applications, 2021, 57(10): 181-186.
[8]	FANG Chengzhi, HUO Xinglong, CHENG Youcheng. Natural Scene Text Detection Combined with Bounding Box Calibration [J]. Computer Engineering and Applications, 2021, 57(1): 161-167.
[9]	WEI Fengtao, SHI Yunpeng, SHI Kun. Backtracking Search Optimization Algorithm with Combined Mutation Strategy [J]. Computer Engineering and Applications, 2020, 56(9): 41-47.
[10]	ZHU Ming, ZHAO Xingyun. Interpolation for Vacant Segments of Segment Maxima Gamut Boundary Descriptor [J]. Computer Engineering and Applications, 2020, 56(8): 192-198.
[11]	FENG Xuegang, ZHOU Dake, YANG Xin. Margin-Maximized Correlation-Filter Based Tracking Method Advanced by Mask Mechanism [J]. Computer Engineering and Applications, 2020, 56(6): 153-158.
[12]	GOU Haiwen, NING Aibing, HU Qin, ZHANG Huizhen. Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties [J]. Computer Engineering and Applications, 2020, 56(24): 43-49.
[13]	WANG Nan, XU Daoyun. Left Ventricular Image Segmentation Algorithm for Weak Edge Information [J]. Computer Engineering and Applications, 2020, 56(23): 211-219.
[14]	TAN Zhenghua, DAI Liping, WEN Yang, LI Guotai. Decision Tree Construction Method Based on Reduction Attribute and Threshold Segmentation [J]. Computer Engineering and Applications, 2020, 56(22): 160-165.
[15]	XU Juan, YAO Rugui, GAO Yan, ZHU Liya. Statistic Characteristics for Upper Bound of Rate Loss with Bounded Channel Estimation Error [J]. Computer Engineering and Applications, 2020, 56(20): 82-86.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics