Network Decomposition And Network Coding

The characterization of the solvability and linear solvability of a network is oneof the most important problem in network coding. It is well known that the problemof determining the solvability of a general network is NP-hard. In this thesis, wedeveloped a region decomposition approach of network and use it to the networkcoding problem of some sub-classes of the non-multicast networks. Our main resultsinclude the following three aspects: 1) We give a simple characterization of thesolvability of two-simple-multicast networks. Our method ensures an algorithm todetermine the solvability of a two-simple-multicast network which can be performedin O(|E|) time. Based on this method, we derive an O(|E|) time algorithm forconstructing the linear network code and a method of constructing the optimalnetwork code. We also derive some useful properties of the optimal network codes.2) We give a simple characterization for linear solvability of the 2-unicast networkswith rate (1, 2), under the condition that the minimum cut from s2to t2is equalto or greater than 3, where s2-t2is the pair of source and sink with rate 2. 3) Wegive a new sufcient and necessary condition for solvability of 3-source 3-terminalsum-networks.It is shown that the region decomposition approach is efective for networkcoding of non-multicast networks.