Paper Info
Title
On the capacity of ms/3t and 3s/nt sum-networks
Abstract
We consider directed acyclic networks where each terminal requires sum of all the sources. Such a class of networks has been termed as sum-networks in the literature. A sum-network having m sources and n terminals has been termed as a ms/nt sum-network. There has been previous works on the capacity of sum-networks, specifically, it has been shown that the capacity of a 3s/3t sum-network is either 0,2/3 or ≥ 1. In this paper, we consider some generalizations of 3s/3t sum-networks, namely, ms/3t and 3s/nt sum-networks, where m, n ≥ 3. For ms/3t and 3s/nt sum-networks, where m, n ≥ 3, if the mincut between each source and each terminal is at least 1, the capacity is known to be at least 2/3. In this paper, we show that there exist ms/3t and 3s/nt sum-networks whose capacities lie between 2/3 and 1. Specifically, we show that for any positive integer k ≥ 2, there exists a ms/3t sum-network (and also a 3s/nt sum-network) whose capacity is k/k+1. We conjecture that the capacity of a ms/3t sum-network, where m > 3 (and also of a 3s/nt sum-network, where n > 3) is either 0, ≥ 1 or of the form k/k+1, where k is a positive integer greater than or equal to 2.
Year
DOI
Venue
2013
10.1109/ITW.2013.6691269
Information Theory Workshop
Keywords
Field
DocType
directed graphs,linear codes,network coding,3s/3t sum-network,3s/nt sum-networks,directed acyclic networks,linear network codes,m sources,ms/3t sum-networks,ms/nt sum-network,n terminals,network coding,positive integer
Integer,Discrete mathematics,Combinatorics,Generalization,Theoretical computer science,Conjecture,Mathematics
Conference
ISBN
Citations 
PageRank 
978-1-4799-1321-3
2
0.40
References 
Authors
14
2
Name
Order
Citations
PageRank
Brijesh Kumar Rai19513.98
Niladri Das2215.70