TY - GEN
T1 - An Edge Reduction Lemma for linear network coding and an application to two-unicast networks
AU - Zeng, Weifei
AU - Cadambe, Viveck Ramesh
AU - Medard, Muriel
PY - 2012/12/1
Y1 - 2012/12/1
N2 - In this paper, we study linear network coding over a wireline network of orthogonal capacitated links represented by a directed acyclic graph. Applying the algebraic framework for linear network coding over Koetter-Médard, we recover an Edge Reduction Lemma - a fundamental connection between edge deletion and the network transfer matrix in the context of the algebraic framework. We study the two-unicast network capacity problem where there are two independent sources and two independent destinations. Using the Edge Reduction Lemma, we make a connection between the linear transfer matrices in the two-unicast setting and the Generalized Network Sharing edge cut bound. Finally, using random linear network coding, we also derive an achievable rate region for the two-unicast problem that is computable purely from the various min-cuts in the graph.
AB - In this paper, we study linear network coding over a wireline network of orthogonal capacitated links represented by a directed acyclic graph. Applying the algebraic framework for linear network coding over Koetter-Médard, we recover an Edge Reduction Lemma - a fundamental connection between edge deletion and the network transfer matrix in the context of the algebraic framework. We study the two-unicast network capacity problem where there are two independent sources and two independent destinations. Using the Edge Reduction Lemma, we make a connection between the linear transfer matrices in the two-unicast setting and the Generalized Network Sharing edge cut bound. Finally, using random linear network coding, we also derive an achievable rate region for the two-unicast problem that is computable purely from the various min-cuts in the graph.
UR - http://www.scopus.com/inward/record.url?scp=84875727069&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84875727069&partnerID=8YFLogxK
U2 - 10.1109/Allerton.2012.6483261
DO - 10.1109/Allerton.2012.6483261
M3 - Conference contribution
AN - SCOPUS:84875727069
SN - 9781467345385
T3 - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012
SP - 509
EP - 516
BT - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012
T2 - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012
Y2 - 1 October 2012 through 5 October 2012
ER -