TY - JOUR

T1 - Alignment-Based Network Coding for Two-Unicast-Z Networks

AU - Zeng, Weifei

AU - Cadambe, Viveck R.

AU - Medard, Muriel

N1 - Funding Information:
This work was supported in part by the Division of Computing and Communication Foundations through the National Science Foundation under Grant 1464336, in part by BAE Systems National Security Solutions, Inc., under Grant 739532-SLIN 0004, in part by Boston University under Grant 20121218112455757, and in part by the Air Force Office of Scientific Research under Grant FA9550-14-1-043 and Grant FA9550-13-1-0023.

PY - 2016/6

Y1 - 2016/6

N2 - In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast-Z network is a two-unicast network where the destination intending to decode the second message has a priori side information of the first message. We make three contributions in this paper. First, we describe a new linear network coding algorithm for two-unicast-Z networks over the directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For the graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and the polynomial complexity in terms of the number of edges. Second, we prove that our algorithm achieves the rate pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over the directed acyclic graphs, to an earlier result of Wang et al., which studied the necessary and sufficient conditions for the feasibility of the rate pair (1, 1) in two-unicast networks. Third, we provide a new proof of the classical max-flow min-cut theorem for the directed acyclic graphs.

AB - In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast-Z network is a two-unicast network where the destination intending to decode the second message has a priori side information of the first message. We make three contributions in this paper. First, we describe a new linear network coding algorithm for two-unicast-Z networks over the directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For the graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and the polynomial complexity in terms of the number of edges. Second, we prove that our algorithm achieves the rate pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over the directed acyclic graphs, to an earlier result of Wang et al., which studied the necessary and sufficient conditions for the feasibility of the rate pair (1, 1) in two-unicast networks. Third, we provide a new proof of the classical max-flow min-cut theorem for the directed acyclic graphs.

UR - http://www.scopus.com/inward/record.url?scp=84976385252&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976385252&partnerID=8YFLogxK

U2 - 10.1109/TIT.2016.2553676

DO - 10.1109/TIT.2016.2553676

M3 - Article

AN - SCOPUS:84976385252

VL - 62

SP - 3183

EP - 3211

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

SN - 0018-9448

IS - 6

M1 - 7452391

ER -