Advances in Mathematics of Communications (AMC)

Network encoding complexity: Exact values, bounds, and inequalities
Pages: 567 - 594, Issue 3, August 2017

doi:10.3934/amc.2017044      Abstract        References        Full text (1272.9K)           Related Articles

Easton Li Xu - Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, United States (email)
Weiping Shang - Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450001, China (email)
Guangyue Han - Department of Mathematics, University of Hong Kong, Pokfulam Road, Hong Kong, China (email)

1 M. Bicknell, A primer on the Pell sequence and related sequences, Fibonacci Quart., 13 (1975), 345-349.       
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.
3 T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd edition, Wiley-Interscience, New York, 2006.       
4 J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19 (1972), 248-264.       
5 R. Graham, B. Rothschild and J. Spencer, Ramsey Theory, 2nd edition, John Wiley Sons, New York, 1990.       
6 G. Han, Menger's paths with minimum mergings, in Proc. 2009 IEEE Inf. Theory Workshop Netw. Inf. Theory, 2009. 271-275.
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.       
8 M. Langberg, A. Sprintson and J. Bruck, The encoding complexity of network coding, IEEE Trans. Inf. Theory, 52 (2006), 2386-2397.       
9 S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inf. Theory, 49 (2003), 371-381.       
10 K. Menger, Zur allgemeinen Kurventheorie, Fundam. Math., 10 (1927), 96-115.
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.       
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
13 A. Tavory, M. Feder and D. Ron, Bounds on linear codes for network multicast, Electr. Colloq. Comput. Complexity, 10 (2003), 1-28.
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.       
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.
16 R. W. Yeung, Information Theory and Network Coding, Springer-Verlag, New York, 2008.
17 R. W. Yeung, S.-Y. R. Li, N. Cai and Z. Zhang, Network Coding Theory, Now Publishers, Delft, Netherlands, 2006.

Go to top