最优广播树

来源 :南京大学 | 被引量 : 0次 | 上传用户:wangfuqun
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
广播问题,从P.J. Slater等人在1977年引入定义以来,至今已经有了非常丰富的内容和巨大进展。广播是信息在网络中传输的一种模式。通过相邻结点间的通讯把初始结点所拥有的信息传输到网络中的每一个结点。广播技术和理论深刻影响通讯、信息论、计算机网络等领域的发展,它本身也越来越成为网络和图论领域的一个重要分支。 广播是一个在通讯网络(作为图的模型)信息传播的过程,而这个信息传输过程是指在满足每一次通信需要一个时间单位和网络中每一个顶点在一个时间单位内至多和它的一个邻点通信这两个条件下把任一个顶点的信息传遍网络中所有顶点。在1998年,Shastri等人研究了广播时间略多于最优时间[log2n]的最稀疏可能的广播图,尤其是他们构造了对于小顶点数n(≤14)的最稀疏可能的广播图和对于较大顶点数n(≤65)的非常稀疏可能的广播图。Shastri猜想对于所有的n,存在一棵广播时间不超过「3/2(log2n+1)」+1的树。在本文中,我们得到较Shastri猜想更强的结果,即对于所有的n,存在一棵广播时间不超过「3/2(log2n+1)」-1的树。进一步的,我们利用了树的中心这一概念研究了对于固定广播时间的树的最大可能结构,得到了固定广播时间的最优广播树,从而给出了具有最优广播时间的任意阶树的的结构。
其他文献
  20年来,并行编译技术的发展说明高性能并行编译系统与高性能体系结构和操作系统等一样,成了高性能计算机系统中不可或缺的一部分。而网络性能的迅速发展,给并行处理技术带来
本文主要研究了两个模型.首先研究了一个白噪声干扰下具有饱和增长率以及两种传染病交叉传染的随机传染病动力学模型.运用自治微分系统的相关理论、定性分析的方法,对具有饱
“Fluid models”是研究排队网络平衡稳定性的重要工具,它在分析何时这样的网络是运行稳定的以及在可能稳定的情形下如何判定其稳定性,定义一个一般性的原则中起着重要的作用。
党的十六届三中全会是我们党在新世纪新阶段召开的一次十分重要的会议。认真学习贯彻全会精神,大力推进改革,努力加快发展,是摆在我们面前的一项重大任务。地方人大及其常委
本文简述了最优恢复问题的相关概念(参看文献【2】或【4】)。设C是线性空间X的子集,I是C到另一线性空间Y的映射,它可以是多值映射。 本文在最后一部分我们研究了另一个最优
  本文系统地考虑和研究了有限区间上重排不变函数空间框架下的鞅不等式和鞅空间。包括重排不变鞅空间及其中的Doob极大不等式,Burkholder-Gundy-Davis不等式,上、下不等式,Ro
一直以来,音乐课容易乱,也常常乱,“乱”通常是指学生在音乐活动中做了与活动无关的事情,或者学生完全忘记了自我,不听从教师的活动安排,从而导致课堂陷入混乱,也影响了音乐
本文全面地讨论了清晰规则,模糊事件,模糊规则的信息量,并将这些新的度量公式成功地应用于数据挖掘。  本文详细讨论了清晰规则信息量的度量,讨论了n元关系的信息熵及其相关性
1892年,俄国力学家李雅谱诺夫(Lyapunov)在他的博士论文《运动稳定性的一般问题》中给出了运动稳定性的严格数学定义和一般方法,从而奠定了稳定性理论的基础.随着科学技术的进步
  考虑带两个需求类的周期检查库存系统:确定的高优先级需求是一个常量,未满足部分按缺货量实行赔偿;随机的低优先级需求是一随机变量,未满足部分视为需求损失。使用配给策略来