最小度生成树的最大度算法

• 作者: 申玉红
• 来源期刊: 云南民族大学学报（自然科学版）
• 学科: 数学
• 关键词: 最小度生成树 近似算法 最大度 破圈
• 年，卷（期）: 2013,（2）
• 所属期刊栏目: 信息与计算机科学
• 页码范围: 144-145
• 页数: 2页
• 分类号: O226|O157.5
• 字数: 1247字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-8513.2013.02.016

摘要

最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	申玉红	德宏师范高等专科学校数学系	19	3	1.0	1.0