# American Institute of Mathematical Sciences

August  2017, 11(3): 567-594. doi: 10.3934/amc.2017044

## Network encoding complexity: Exact values, bounds, and inequalities

 1 Department of Electrical and Computer Engineering, Texas A & M University, College Station, TX 77843, USA 2 Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450001, China 3 Department of Mathematics, University of Hong Kong, Pokfulam Road, Hong Kong, China

Results of this paper have been partially presented in the 49th Allerton Conference on Communication, Control and Computing [15], and the 2012 International Symposium on Information Theory and its Applications [14]

Received  November 2015 Revised  September 2016 Published  August 2017

Fund Project: The last author would like to thank the support from the University Grants Committee of the Hong Kong Special Administrative Region, China under grant No. AoE/E-02/08 and the support from Research Grants Council of the Hong Kong Special Administrative Region, China under grant No. 17301814.

For an acyclic directed network with multiple pairs of sources and sinks and a set of Menger's paths connecting each pair of source and sink, it is known that the number of mergings among these Menger's paths is closely related to network encoding complexity. In this paper, we focus on networks with two pairs of sources and sinks and we derive bounds on and exact values of two functions relevant to encoding complexity for such networks.

Citation: Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044
##### References:

show all references

##### References:
Paths $\beta_1, \beta_2$ merge at edge $A \to B$ and at merged subpath (or merging) $A \to B \to C \to D$, and paths $\beta_1, \beta_2, \beta_3$ merge at edge $B \to C$ and at merged subpath (or merging) $B\to C$ (Here, arrows in the figure represents edges, and the terminal points of arrows should be naturally interpreted as vertices; the same convention applies to other figures in this paper)
(a) Network coding in the butterfly network (b) Network coding in a two-way channel (c) Network coding in two sessions of unicast
An example of a reroutable graph
Two examples of merging sequences (as in Remark 3.3, all the mergings in this figure are represented by solid dots instead)
Two examples of alternating sequences
(a) A non-reroutable (2, 3)-graph with 8 mergings (b) An example of a (2, 5)-graph
Graph $\mathcal{E}(4, 4)$ with $9$ mergings
(a) Graph $\mathcal{F}(3, 3)$ with $11$ mergings (b) Splitting of $R_1$ in $\mathcal{F}(3, 3)$
Concatenation of $\mathcal{F}(2, 2)$ and a non-reroutable $(2, 2)$-graph
Partition a $(3, c_2)$-graph into blocks
Case 1
Case 2
Concatenation of two (3, 3)-graphs
Concatenation of a (2, 2)-graph and a (4, 4)-graph
 [1] Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 [2] Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 [3] Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044 [4] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 0.734