| 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 |
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.
| [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.
doi: 10.1109/TIT.2005.847712. |
| [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. |
| [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. |
| [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.
doi: 10.1109/TIT.2013.2262492. |
| [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.
doi: 10.1007/978-1-4614-1800-9_176. |
| [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. |
show all references
| [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.
doi: 10.1109/TIT.2005.847712. |
| [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. |
| [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. |
| [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.
doi: 10.1109/TIT.2013.2262492. |
| [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.
doi: 10.1007/978-1-4614-1800-9_176. |
| [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. |
| [1] |
Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577 |
| [2] |
Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021027 |
| [3] |
Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145 |
| [4] |
Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95 |
| [5] |
Kashi Behrstock, Michel Benaïm, Morris W. Hirsch. Smale strategies for network prisoner's dilemma games. Journal of Dynamics and Games, 2015, 2 (2) : 141-155. doi: 10.3934/jdg.2015.2.141 |
| [6] |
F. Ali Mehmeti, R. Haller-Dintelmann, V. Régnier. Dispersive waves with multiple tunnel effect on a star-shaped network. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 783-791. doi: 10.3934/dcdss.2013.6.783 |
| [7] |
Michelle L.F. Cheong, Rohit Bhatnagar, Stephen C. Graves. Logistics network design with supplier consolidation hubs and multiple shipment options. Journal of Industrial and Management Optimization, 2007, 3 (1) : 51-69. doi: 10.3934/jimo.2007.3.51 |
| [8] |
Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial and Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251 |
| [9] |
Fabio Bagagiolo, Rosario Maggistro, Raffaele Pesenti. Origin-to-destination network flow with path preferences and velocity controls: A mean field game-like approach. Journal of Dynamics and Games, 2021, 8 (4) : 359-380. doi: 10.3934/jdg.2021007 |
| [10] |
Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics and Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016 |
| [11] |
Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149 |
| [12] |
T. S. Evans, A. D. K. Plato. Network rewiring models. Networks and Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221 |
| [13] |
David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161. |
| [14] |
Pradeep Dubey, Rahul Garg, Bernard De Meyer. Competing for customers in a social network. Journal of Dynamics and Games, 2014, 1 (3) : 377-409. doi: 10.3934/jdg.2014.1.377 |
| [15] |
Suzana Antunović, Tonči Kokan, Tanja Vojković, Damir Vukičević. Exponential generalised network descriptors. Advances in Mathematics of Communications, 2019, 13 (3) : 405-420. doi: 10.3934/amc.2019026 |
| [16] |
Yassine El Gantouh, Said Hadd, Abdelaziz Rhandi. Approximate controllability of network systems. Evolution Equations and Control Theory, 2021, 10 (4) : 749-766. doi: 10.3934/eect.2020091 |
| [17] |
Jianfeng Feng, Mariya Shcherbina, Brunello Tirozzi. Stability of the dynamics of an asymmetric neural network. Communications on Pure and Applied Analysis, 2009, 8 (2) : 655-671. doi: 10.3934/cpaa.2009.8.655 |
| [18] |
Zari Dzalilov, Iradj Ouveysi, Alexander Rubinov. An extended lifetime measure for telecommunication network. Journal of Industrial and Management Optimization, 2008, 4 (2) : 329-337. doi: 10.3934/jimo.2008.4.329 |
| [19] |
Shruti Agarwal, Gilles Carbou, Stéphane Labbé, Christophe Prieur. Control of a network of magnetic ellipsoidal samples. Mathematical Control and Related Fields, 2011, 1 (2) : 129-147. doi: 10.3934/mcrf.2011.1.129 |
| [20] |
Proscovia Namayanja. Chaotic dynamics in a transport equation on a network. Discrete and Continuous Dynamical Systems - B, 2018, 23 (8) : 3415-3426. doi: 10.3934/dcdsb.2018283 |
2020 Impact Factor: 0.935
[Back to Top]
