论文摘要
很多领域产生的大量数据都可以很自然地用不确定图模型表示和描述,如蛋白质交互网络、社交网络、无线传感器网络等。本文研究不确定图上最可靠的最小生成树问题,该问题具有广泛的应用价值和研究意义。精确地求解算法需要枚举所有可能的最小生成树并找出其中出现次数最多的那个。因此,枚举开销随着边数增多呈指数增长,当图规模较大时并不可行。为此本文提出了一个时间复杂度为O(d|V|~2)的启发式贪心算法,其中d为最大的顶点度数,|V|为顶点数。实验结果表明,该算法具有较好的效率和较高扩展性。
论文目录
文章来源
类型: 期刊论文
作者: 张安珍,李建中
关键词: 不确定图,最可靠最小生成树,贪心算法
来源: 智能计算机与应用 2019年06期
年度: 2019
分类: 信息科技,基础科学
专业: 数学,计算机软件及计算机应用
单位: 哈尔滨工业大学计算机科学与技术学院
基金: 国家自然科学基金(61190115,61033015),国家重点基础研究发展计划(973)(2012CB316200)
分类号: O157.5;TP301.6
页码: 1-5+12
总页数: 6
文件大小: 1261K
下载量: 257
相关论文文献
标签：不确定图论文; 最可靠最小生成树论文; 贪心算法论文;