一种改进的Steiner树启发式算法

来源 :通信学报 | 被引量 : 0次 | 上传用户：yanghaibin123

【摘要】

：

最小Steiner树问题是NP完全问题,关于Steiner问题的启发式算法的研究具有重要理论和实际意义.本文在 MPH算法的基础上,对于经过某些关键节点的短路径优先考虑,提出了KBMPH算

【作者】

：

余燕平

【机构】

：

浙江大学信息与电子工程学系

【出处】

：

通信学报

【发表日期】

：

2002年11期

【关键词】

：

STEINER树启发式算法多播路由算法 MPH算法 NP完全问题多播树通信网络 multicast routing algorithm Steiner

【基金项目】

：

浙江省重点实验室基金

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

最小Steiner树问题是NP完全问题,关于Steiner问题的启发式算法的研究具有重要理论和实际意义.本文在 MPH算法的基础上,对于经过某些关键节点的短路径优先考虑,提出了KBMPH算法,从而实现更多链路的共享.在随机网络上的仿真结果表明,极大多数情况下,在准Steiner树的网络费用上KBMPH算法优于MPH算法,KBMPH算法的复杂度为.

其他文献

隶属云辛普森模型在跳频码发生器中的应用

隶属云模型是定性和定量之间转换的工具，用其数字特征的期望值E，熵σ，超熵h三个数值建立了辛普森云模型和变形辛普森云模型，分析了模型的统计分布，导出了概率密度公式，实现了它们在

期刊

跳频码发生器隶属云模型辛普森分布概率密度函数人工智能控制通信抗干扰membership cloud modelsXinpson distribut

自相似业务下视频服务器的接纳控制

VOD 系统中,有限的磁盘 I/O 带宽或缓存空间往往成为系统的瓶颈。针对这一问题,提出了自相似业务下视频服务器的接纳控制算法。该算法运用等效带宽理论,通过在线测量系统所剩资源和周期容限的幅度变化来实时调节调度周期的大小,使得系统所剩资源达到动态的“等量”平衡。仿真结果表明,该算法不但简化了接纳过程,节约了系统资源,提高了算法的可实现性,而且系统的接纳率比 Lee,Yeom 所提算法的接纳率提高了

期刊

接纳控制自相似动态调度周期等效带宽admission control self-similar dynamic scheduling period

淮阴师范学院计算机科学系

期刊

计算机科学系师范学院淮阴计算机科学与技术网络工程

移动通信增值服务认证和支付研究

描述了一种适用于移动通信增值服务的认证和支付模型,提供了用户和增值服务提供者之间的双向身份认证机制;利用小额支付中的散列链概念,很好地解决了增值服务的支付问题,并具有一定的防欺骗性。

期刊

移动通信增值服务认证支付mobile communication VAS authentication payment1

多SCP智能网的负载控制模型与算法

由于智能网的主要瓶颈是SCP的处理能力,因此本文提出了多SCPs智能网及其负载控制模型,并分析了该模型的负载控制要求。由于在智能网中引入了多SCP,因此对呼叫分发(路由)进行了讨论,提出了一种实用的负载控制算法。最后给出了模拟结果。

期刊

SCP智能网多业务控制点负载控制过载控制intelligent networksmulti-SCPload controloverload co

多径条件下最小方差空时多用户检测的性能分析

本文研究和分析了在一般多径信道条件下,CDMA阵列接收机对于多址干扰和符号间串扰的联合抑制。文中推广了多用户检测的正则表示,利用最小最大原理实现了广义正则形式的最小方差空时多用户检测器;进一步分析并改进了空时信道的估计方法;最后定量分析了系统的干扰抑制能力。

期刊

码分多址多用户检测移动通信多径条件最小方差CDMAspace-time processingmultiuser detectioninterfe

波分复用无源光网络中用户随机接入的性能估计

本文提出了在波分复用无源光网络（VDMPON）中，用户接入采用随接入的新方式，分析了网络性能。同时，为了改善随机网络的网络性能，首次提出了跳波长随机接入的方法。通过文中的数值结果

期刊

波分复用无源光网络随机接入光纤通信性能估计OANPONWDMPONrandom accessthroughoutdelay

公钥证书撤消机制综述

如何撤消证书一直是公钥基础设施(PKI)研究和应用中的一个难点问题。本文对目前应用和研究中的证书撤消机制进行了综述,详细描述了各种机制的工作原理,并对各种机制的优缺点进行了详细剖析。1

期刊

公钥基础设施认证中心证书撤消证书撤消列表在线证书状态协议public key infrastructure certification author

立体图像序列的压缩方法

首先介绍了立体视觉的基本原理,然后对立体图像的压缩方法分四类进行了综述。对其中用于立体图像序列的两种主要方法:基于“块”匹配的立体图像压缩方法和基于物体的立体图像压缩方法进行了深入探讨。通过对已有成果进行总结和分类,剖析了两种方法的优、缺点,并提出了一些还需要深入研究的问题,如:残差图像编码、遮挡检测、更精确的场景分割等。1

期刊

立体视觉图像压缩块匹配物体基stereo vision image compression block matching object-based

用NCP逻辑分析LMDS的PKM协议

使用NCP逻辑分析了LMDS的PKM协议,发现该协议容易遭到伪造BS攻击,也可能遭到AK重传攻击。这些是由协议过程中消息的结构不完善引起的。本文在PKM协议提供的安全措施的基础上,针对上述不足提出了更改部分消息结构的解决方案。

期刊

协议安全PKM协议NCP逻辑LMDSprotocol security PKM protocol NCP logic LMDS

一种改进的Steiner树启发式算法

与本文相关的学术论文