Computer Science – Information Theory
Scientific paper
2010-07-17
Computer Science
Information Theory
Scientific paper
The encoding complexity for network coding with one multicast session has been intensively studied from several aspects: e.g., the time complexity, the required number of encoding links and the required field size for a linear code solution. However, these issues are less understood for the network with multiple multicast sessions. Recently, C. C. Wang and N. B. Shroff declared that polynomial time can decide the solvability of the two simple multicast network coding (2-SMNC) problem. In this paper, we prove for the 2-SMNC networks: $1)$ the solvability can be determined with time $O(|E|)$; $2)$ a solution can be constructed with time $O(|E|)$; $3)$ an optimal solution can be obtained in polynomial time; $4)$ the number of encoding links required to achieve a solution is upper-bounded by $\max\{3,2N-2\}$; and $5)$ the field size required to achieve a linear solution is upper-bounded by $\max\{2,\lfloor\sqrt{2N-7/4}+1/2\rfloor\}$, where $|E|$ is the number of links and $N$ is the number of sinks of the underlying network. The bounds are shown to be tight and the algorithms to determine the solvability, to construct a solution and to construct an optimal solution are proposed.
Cai Kai
Feng Rongquan
Song Wentu
No associations
LandOfFree
Encoding Complexity of Network Coding with Two Simple Multicast Sessions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Encoding Complexity of Network Coding with Two Simple Multicast Sessions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding Complexity of Network Coding with Two Simple Multicast Sessions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-658968