On the Solvability of 2-pair Unicast Networks --- A Cut-based Characterization

Abstract

In this paper, we propose a subnetwork decomposition/combination approach to investigate the single rate $2$-pair unicast problem. It is shown that the solvability of a $2$-pair unicast problem is completely determined by four specific link subsets, namely, ${\mathcal{A}}_{1,1}$, ${\mathcal{A}}_{2,2}$, ${\mathcal{A}}_{1,2}$ and ${\mathcal{A}}_{2,1}$ of its underlying network. As a result, an efficient cut-based algorithm to determine the solvability of a $2$-pair unicast problem is presented.

15 pages

Cited by in corpus (1)

• Multiple Unicast Capacity of 2-Source 2-Sink Networks