American Institute of Mathematical Sciences

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

Network encoding complexity: Exact values, bounds, and inequalities

Easton Li Xu , Weiping Shang 2, and  Guangyue Han 3,

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.

Keywords: Menger's path, network coding, encoding complexity, multicast network, multiple unicast network.
Mathematics Subject Classification: Primary: 94A29; Secondary: 05C40.
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:
[1]

M. Bicknell, A primer on the Pell sequence and related sequences, Fibonacci Quart., 13 (1975), 345-349.   Google Scholar

[2]

K. Cai, K. B. Letaief, P. Fan and R. Feng, On the solvability of 2-pair networks – a cut-based characterization, Phys. Commun., 6 (2013), 124-133.   Google Scholar

[3]

T. M. Cover and J. A. Thomas, Elements of Information Theory 2nd edition, Wiley-Interscience, New York, 2006.  Google Scholar

[4]

J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19 (1972), 248-264.   Google Scholar

[5]

R. Graham, B. Rothschild and J. Spencer, Ramsey Theory 2nd edition, John Wiley Sons, New York, 1990.  Google Scholar

[6]

G. Han, Menger's paths with minimum mergings, in Proc. 2009 IEEE Inf. Theory Workshop Netw. Inf. Theory, 2009. 271–275. Google Scholar

[7]

S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain and L. Tolhuizen, Polynomial time algorithms for multicast network code construction, IEEE Trans. Inf. Theory, 51 (2005), 1973-1982.  doi: 10.1109/TIT.2005.847712.  Google Scholar

[8]

M. Langberg, A. Sprintson and J. Bruck, The encoding complexity of network coding, IEEE Trans. Inf. Theory, 52 (2006), 2386-2397.  doi: 10.1109/TIT.2006.874434.  Google Scholar

[9]

S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inf. Theory, 49 (2003), 371-381.  doi: 10.1109/TIT.2002.807285.  Google Scholar

[10]

K. Menger, Zur allgemeinen Kurventheorie, Fundam. Math., 10 (1927), 96-115.   Google Scholar

[11]

W. Song, K. Cai, R. Feng and R. Wang, The complexity of network coding with two unit-rate multicast sessions, IEEE Trans. Inf. Theory, 59 (2003), 5692-5707.  doi: 10.1109/TIT.2013.2262492.  Google Scholar

[12]

W. Song, K. Cai, C. Yuen and R. Feng, On the solvability of 3s/nt sum-network – a region decomposition and weak decentralized code method, preprint, arXiv: 1502.00762 Google Scholar

[13]

A. Tavory, M. Feder and D. Ron, Bounds on linear codes for network multicast, Electr. Colloq. Comput. Complexity, 10 (2003), 1-28.   Google Scholar

[14]

E. L. Xu, W. Shang and G. Han, A graph theoretical approach to network encoding complexity, in Proc. 2012 Int. Symp. Inf. Theory Appl. , 2012,396–400. doi: 10.1007/978-1-4614-1800-9_176.  Google Scholar

[15]

L. Xu and G. Han, Bounds and exact values in network encoding complexity with two sinks, in Proc. 49th Ann. Allerton Conf. Commun. Control Comput. , 2011,1462–1469. Google Scholar

[16]

R. W. Yeung, Information Theory and Network Coding Springer-Verlag, New York, 2008. Google Scholar

[17]

R. W. Yeung, S. -Y. R. Li, N. Cai and Z. Zhang, Network Coding Theory Now Publishers, Delft, Netherlands, 2006. Google Scholar

show all references

References:
[1]

M. Bicknell, A primer on the Pell sequence and related sequences, Fibonacci Quart., 13 (1975), 345-349.   Google Scholar

[2]

K. Cai, K. B. Letaief, P. Fan and R. Feng, On the solvability of 2-pair networks – a cut-based characterization, Phys. Commun., 6 (2013), 124-133.   Google Scholar

[3]

T. M. Cover and J. A. Thomas, Elements of Information Theory 2nd edition, Wiley-Interscience, New York, 2006.  Google Scholar

[4]

J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19 (1972), 248-264.   Google Scholar

[5]

R. Graham, B. Rothschild and J. Spencer, Ramsey Theory 2nd edition, John Wiley Sons, New York, 1990.  Google Scholar

[6]

G. Han, Menger's paths with minimum mergings, in Proc. 2009 IEEE Inf. Theory Workshop Netw. Inf. Theory, 2009. 271–275. Google Scholar

[7]

S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain and L. Tolhuizen, Polynomial time algorithms for multicast network code construction, IEEE Trans. Inf. Theory, 51 (2005), 1973-1982.  doi: 10.1109/TIT.2005.847712.  Google Scholar

[8]

M. Langberg, A. Sprintson and J. Bruck, The encoding complexity of network coding, IEEE Trans. Inf. Theory, 52 (2006), 2386-2397.  doi: 10.1109/TIT.2006.874434.  Google Scholar

[9]

S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inf. Theory, 49 (2003), 371-381.  doi: 10.1109/TIT.2002.807285.  Google Scholar

[10]

K. Menger, Zur allgemeinen Kurventheorie, Fundam. Math., 10 (1927), 96-115.   Google Scholar

[11]

W. Song, K. Cai, R. Feng and R. Wang, The complexity of network coding with two unit-rate multicast sessions, IEEE Trans. Inf. Theory, 59 (2003), 5692-5707.  doi: 10.1109/TIT.2013.2262492.  Google Scholar

[12]

W. Song, K. Cai, C. Yuen and R. Feng, On the solvability of 3s/nt sum-network – a region decomposition and weak decentralized code method, preprint, arXiv: 1502.00762 Google Scholar

[13]

A. Tavory, M. Feder and D. Ron, Bounds on linear codes for network multicast, Electr. Colloq. Comput. Complexity, 10 (2003), 1-28.   Google Scholar

[14]

E. L. Xu, W. Shang and G. Han, A graph theoretical approach to network encoding complexity, in Proc. 2012 Int. Symp. Inf. Theory Appl. , 2012,396–400. doi: 10.1007/978-1-4614-1800-9_176.  Google Scholar

[15]

L. Xu and G. Han, Bounds and exact values in network encoding complexity with two sinks, in Proc. 49th Ann. Allerton Conf. Commun. Control Comput. , 2011,1462–1469. Google Scholar

[16]

R. W. Yeung, Information Theory and Network Coding Springer-Verlag, New York, 2008. Google Scholar

[17]

R. W. Yeung, S. -Y. R. Li, N. Cai and Z. Zhang, Network Coding Theory Now Publishers, Delft, Netherlands, 2006. Google Scholar

Figure 1.  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)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  (a) Network coding in the butterfly network (b) Network coding in a two-way channel (c) Network coding in two sessions of unicast
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  An example of a reroutable graph
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Two examples of merging sequences (as in Remark 3.3, all the mergings in this figure are represented by solid dots instead)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Two examples of alternating sequences
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  (a) A non-reroutable (2, 3)-graph with 8 mergings (b) An example of a (2, 5)-graph
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Graph $\mathcal{E}(4, 4)$ with $9$ mergings
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  (a) Graph $\mathcal{F}(3, 3)$ with $11$ mergings (b) Splitting of $R_1$ in $\mathcal{F}(3, 3)$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Concatenation of $\mathcal{F}(2, 2)$ and a non-reroutable $(2, 2)$-graph
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  Partition a $(3, c_2)$-graph into blocks
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  Case 1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 12.  Case 2
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 13.  Concatenation of two (3, 3)-graphs
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 14.  Concatenation of a (2, 2)-graph and a (4, 4)-graph
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021009
[2]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[3]

Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159
[4]

Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021016
[5]

Cheng-Kai Hu, Fung-Bao Liu, Hong-Ming Chen, Cheng-Feng Hu. Network data envelopment analysis with fuzzy non-discretionary factors. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1795-1807. doi: 10.3934/jimo.2020046
[6]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[7]

Saeed Assani, Muhammad Salman Mansoor, Faisal Asghar, Yongjun Li, Feng Yang. Efficiency, RTS, and marginal returns from salary on the performance of the NBA players: A parallel DEA network with shared inputs. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021053
[8]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066
[9]

Ru Li, Guolin Yu. Strict efficiency of a multi-product supply-demand network equilibrium model. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2203-2215. doi: 10.3934/jimo.2020065
[10]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022
[11]

Kai Cai, Guangyue Han. An optimization approach to the Langberg-Médard multiple unicast conjecture. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021001
[12]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637
[13]

Yi Gao, Rui Li, Yingjing Shi, Li Xiao. Design of path planning and tracking control of quadrotor. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021063
[14]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021035
[15]

Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061
[16]

Sheng-I Chen, Yen-Che Tseng. A partitioning column approach for solving LED sorter manipulator path planning problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021055
[17]

Yongkun Wang, Fengshou He, Xiaobo Deng. Multi-aircraft cooperative path planning for maneuvering target detection. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021050
[18]

Skyler Simmons. Stability of Broucke's isosceles orbit. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3759-3779. doi: 10.3934/dcds.2021015
[19]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521
[20]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (92)
  • HTML views (59)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences