不确定图最小生成树算法

• 作者: 张安珍 李建中
• 来源期刊: 智能计算机与应用
• 学科: 工学
• 关键词: 不确定图 最可靠最小生成树 贪心算法
• 年，卷（期）: 2019,（6）
• 所属期刊栏目: 学术研究与应用
• 页码范围: 1-5,12
• 页数: 6页
• 分类号: TP391.41
• 字数: 4355字
• 语种: 中文

摘要

很多领域产生的大量数据都可以很自然地用不确定图模型表示和描述,如蛋白质交互网络、社交网络、无线传感器网络等.本文研究不确定图上最可靠的最小生成树问题,该问题具有广泛的应用价值和研究意义.精确地求解算法需要枚举所有可能的最小生成树并找出其中出现次数最多的那个.因此,枚举开销随着边数增多呈指数增长,当图规模较大时并不可行.为此本文提出了一个时间复杂度为O(d|V|2)的启发式贪心算法,其中d为最大的顶点度数,|V|为顶点数.实验结果表明,该算法具有较好的效率和较高扩展性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	哈尔滨工业大学计算机科学与技术学院	237	6003	33.0	72.0
2	张安珍	哈尔滨工业大学计算机科学与技术学院	3	18	1.0	3.0