网络分解在网络编码中的应用

来源 :北京大学 | 被引量 : 0次 | 上传用户:dejia2000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
网络的可解性刻画,或者说,网络编码的存在性问题,是网络编码研究中的最基本问题之一.众所周知,非组播网络的网络编码存在性判定问题是NP难的.在本文中,我们发展了一套网络分解的方法并用来研究了非组播网络的几个多项式时间可解的子类.我们的结果主要包括下面三个:1)对于具有两个简单组播的网络,我们给出了其可解性的一个简单的刻画方法.利用这个方法,我们给出了O(|E|)时间的算法来判定网络的可解性和构造其线性网络编码,其中E为网络边集.同时我们给出了构造极小网络编码的方法并给出了极小网络编码的一些有用的性质.2)对于熵率为(1,2)的2-单播网络,在假设s2-t2的割容量大于或等于3的条件下,我们给出了其线性可解性的一个简单的刻画,其中s2-t2是熵率为2的单播会话的源节点-目标节点组成的对.3)对于具有3个源节点和3个目标节点的和网络,我们给出了其线性可解性的一个简单的刻画.  研究结果表明,网络分解方法是研究非组播网络的网络编码问题的一种有效方法.
其他文献
数字签名是信息安全领域的一个重要研究方向,它在身份识别与认证、数据完整性保护和抗否认等方面具有其它技术无法替代的作用。作为手写签名的模拟和扩展,数字签名广泛应用于
令F表示q个元素的有限域,这里q是2的一个方幂,n≥2是一个整数.令M是F上全体n×n矩阵的集合,K表示F上全体n×n交错矩阵的集合.A,B(∈M(,n))关于K同余,如果A+B∈K,这时记为A≡B