Skip to main content
Article
Sum-Networks from Undirected Graphs: Construction and Capacity Analysis
2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014
  • Ardhendu S. Tripathy, Missouri University of Science and Technology
  • Aditya Ramamoorthy
Abstract

We consider a directed acyclic network with multiple sources and multiple terminals where each terminal is interested in decoding the sum of independent sources generated at the source nodes. We describe a procedure whereby a simple undirected graph can be used to construct such a sum-network and demonstrate an upper bound on its computation rate. Furthermore, we show sufficient conditions for the construction of a linear network code that achieves this upper bound. Our procedure allows us to construct sum-networks that have any arbitrary computation rate p/q (where p, q are non-negative integers). Our work significantly generalizes a previous approach for constructing sum-networks with arbitrary capacities. Specifically, we answer an open question in prior work by demonstrating sum-networks with significantly fewer number of sources and terminals.

Meeting Name
52nd Allerton Conference on Communication, Control, and Computing (2014: Sep. 30-Oct. 3, Monticello, IL)
Department(s)
Computer Science
International Standard Book Number (ISBN)
978-147998009-3
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2014 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
10-3-2014
Publication Date
03 Oct 2014
Disciplines
Citation Information
Ardhendu S. Tripathy and Aditya Ramamoorthy. "Sum-Networks from Undirected Graphs: Construction and Capacity Analysis" 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014 (2014) p. 651 - 658
Available at: http://works.bepress.com/ardhendu-s-tripathy/14/