Abstract: Based on the linear network coding, this paper proposes the maximum decodable linear network coding. It proves that whether there exists a maximum decodable linear network code for a given network is NP-hard, and gives an approximate polynomial algorithm with a heuristic rule to construct such a network code. Simulation proves that the maximum decodable linear network coding helps to gain better network capacity.

Key words: network coding, maximum decodable, complexity, construction

摘要： 在传统线性网络编码的基础上提出一种网络编码，即最大可解线性网络编码，并证明对于一个给定网络，判定是否存在一个最大可解线性网络编码是NP-困难问题，给出单源情况下该网络编码的启发式近似构造算法。实验模拟证明，相比传统线性多播网络编码，采用最大可解线性网络编码的网络容量有了较大的提高。

关键词: 网络编码, 最大可解, 复杂性, 构造

CLC Number: 

• TP393