A Graph-Theoretic Characterization oftheFeasibility of Network Coding withTwo Simple Unicast Sessions
Chih-Chun Wang · 2007
Theproblemofnetwork coding withtwosimple unicast sessions isconsidered forgeneral directed acyclic graphs. An explicit graph-theoretic characterization isprovided forthe feasibility ofwhether twosymbols atdifferent sources canbe simultaneously transmitted tothedesignated sinks vianetwork coding. Theexistence ofarouting schemeisequivalent tofinding edge-disjoint paths. Similarly, inthis paperitisproven thatthe existence ofa networkcoding schemeisequivalent tofinding pathswithcontrolled edgeoverlaps, andthecharacterization includes thewell-studied butterfly graphasaspecial case. Various generalizations andimplications arediscussed basedon the constructive natureoftheflow-based conditions. Forexample, itisshownthatalinear network coding schemeusing onlysix paths isaseffective asanynon-linear network coding scheme.