Sum-Networks From Incidence Structures: Construction and Capacity Analysis
作者： Ardhendu Tripathy , Aditya Ramamoorthy
关键词:
摘要: A sum-network is an instance of a function computation problem over directed acyclic network, in which each terminal node wants to compute the sum finite field information observed at all source nodes. Many characteristics well-studied multiple unicast network communication also hold for sum-networks, due known reduction between two problems. In this paper, we describe algorithm construct families instances using incidence structures. The capacity several these evaluated. Unlike coding problem, sum-networks depends on characteristic computed. This dependence very strong; show examples that have rate-1 solution one but rate close zero different characteristic. addition, can arbitrarily capacities alphabets.
harvard.edu
arxiv.org
sci-hub.se 参考文章(33)
Rathinakumar Appuswamy, Massimo Franceschetti, Nikhil Karamchandani, Kenneth Zeger, Linear Codes, Target Function Classes, and Network Computing Capacity IEEE Transactions on Information Theory. ,vol. 59, pp. 5741- 5753 ,(2013) , 10.1109/TIT.2013.2252052
Richard A. Brualdi, Combinatorial Matrix Classes ,(1991)
Cupjin Huang, Zihan Tan, Shenghao Yang, Upper bound on function computation in directed acyclic networks information theory workshop. pp. 1- 5 ,(2015) , 10.1109/ITW.2015.7133086
Ardhendu Tripathy, Aditya Ramamoorthy, Capacity of sum-networks for different message alphabets international symposium on information theory. pp. 606- 610 ,(2015) , 10.1109/ISIT.2015.7282526
Douglas R. Stinson, Combinatorial Designs: Constructions and Analysis ,(2003)
Shurui Huang, A. Ramamoorthy, An Achievable Region for the Double Unicast Problem Based on a Minimum Cut Analysis IEEE Transactions on Communications. ,vol. 61, pp. 2890- 2899 ,(2013) , 10.1109/TCOMM.2013.053013.120542
Luc Teirlinck, Non-trivial t-designs without repeated blocks exist for all t Discrete Mathematics. ,vol. 306, pp. 1060- 1067 ,(2006) , 10.1016/J.DISC.2006.03.024
April Rasala Lehman, Eric Lehman, Complexity classification of network information flow problems symposium on discrete algorithms. pp. 142- 150 ,(2004) , 10.5555/982792.982814
J. Korner, K. Marton, How to encode the modulo-two sum of binary sources (Corresp.) IEEE Transactions on Information Theory. ,vol. 25, pp. 219- 221 ,(1979) , 10.1109/TIT.1979.1056022
Shurui Huang, Aditya Ramamoorthy, On the Multiple-Unicast Capacity of 3-Source, 3-Terminal Directed Acyclic Networks IEEE ACM Transactions on Networking. ,vol. 22, pp. 285- 299 ,(2014) , 10.1109/TNET.2013.2270438