A Graph Theoretical Approach to Network Encoding Complexity

Li Xu, Weiping Shang, Guangyue Han

Consider an acyclic directed network $G$ with sources $S_1,S_2,...,S_l$ and distinct sinks $R_1,R_2,...,R_l$. For $i=1,2,...,l$, let $c_i$ denote the min-cut between $S_i$ an…