Link Decomposition of Network Coding
Kai Cai, Pingyi Fan · 2006
In this paper, we investigate the link failure problem of network coding for point-to-point networks, multicast networks, and multi-source multi-sink networks, respectively. We decompose the total network link space into three disjoint parts such as the A-set, the B-set and another one, where the A-set include the most important edges to the network capacity and the B-set include the edges having less influence on the network capacity. It is shown that the A-set and B-set of a network can be found out in polynomial time. According to the results of link decomposition, some basic algebraic structures of the link failure space are proposed