On the Solvability of 3s/nt Sum-Network - A Region Decomposition and Weak Decentralized Code Method.

摘要: We study the network coding problem of sum-networks with 3 sources and n terminals (3s/nt sum-network), for an arbitrary positive integer n, derive a sufficient necessary condition solvability family so-called terminal-separable sum-network. Both sum-network can be decided in polynomial time. Consequently, we give another condition, which yields faster (O(|E|) time) algorithm than that Shenvi Dey ([18], (O(|E|^3) time), to determine 3s/3t To obtain results, further develop region decomposition method [22], [23] generalize decentralized [21]. Our methods provide new efficient tools multiple source sink problems.