期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到1篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
图的Steiner树问题的改进的快速近似算法
1
作者 吕其诚 《黑龙江大学自然科学学报》 CAS 1996年第3期40-42,共3页
设Ｇ＝（Ｖ，Ｅ）是一个边皆有非负权的连通无向图，设Ｚ是Ｇ的结点集Ｖ的子集。一个最小Ｓｔｅｉｎｅｒ树是Ｇ的连通子图，它含有Ｚ的全部结点，且是有最小边权和的树。一个启发式算法结果分别由ＥＩ—Ａｒｂｉ，ｐｌｅｓｎｉｋ和ｋｏ... 设Ｇ＝（Ｖ，Ｅ）是一个边皆有非负权的连通无向图，设Ｚ是Ｇ的结点集Ｖ的子集。一个最小Ｓｔｅｉｎｅｒ树是Ｇ的连通子图，它含有Ｚ的全部结点，且是有最小边权和的树。一个启发式算法结果分别由ＥＩ—Ａｒｂｉ，ｐｌｅｓｎｉｋ和ｋｏｕ等人给出，按该算法得到的Ｓｔｅｉｎｅｒ树与最小Ｓｔｅｉｎｅｒ树最多只差一常数因子２（１—１／ｚ），这里ｚ＝｜Ｚ｜。该算法要计算出ｚ个单源最短路径且算法的时间复杂度为Ｏ（ｚ（ｎｌｏｇｎ＋ｍ）），这里ｎ＝｜Ｖ｜，ｍ＝｜Ｅ｜。现在我们给出了一个改进的算法，其算法性能仍是２（１—１／ｚ），但它只需计算一个单源最短路径且其时间复杂度为Ｏ（ｎｌｏｇｎ＋ｍ），较显著地降低了复杂度的阶数。 展开更多
关键词 图 连通子图 STEINER树 快速近似算法
在线阅读 下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部