论文部分内容阅读
网络的可解性刻画,或者说,网络编码的存在性问题,是网络编码研究中的最基本问题之一.众所周知,非组播网络的网络编码存在性判定问题是NP难的.在本文中,我们发展了一套网络分解的方法并用来研究了非组播网络的几个多项式时间可解的子类.我们的结果主要包括下面三个:1)对于具有两个简单组播的网络,我们给出了其可解性的一个简单的刻画方法.利用这个方法,我们给出了O(|E|)时间的算法来判定网络的可解性和构造其线性网络编码,其中E为网络边集.同时我们给出了构造极小网络编码的方法并给出了极小网络编码的一些有用的性质.2)对于熵率为(1,2)的2-单播网络,在假设s2-t2的割容量大于或等于3的条件下,我们给出了其线性可解性的一个简单的刻画,其中s2-t2是熵率为2的单播会话的源节点-目标节点组成的对.3)对于具有3个源节点和3个目标节点的和网络,我们给出了其线性可解性的一个简单的刻画. 研究结果表明,网络分解方法是研究非组播网络的网络编码问题的一种有效方法.