On the capacity of ms/3t and 3s/nt sum-networks
Brijesh Kumar Rai, Niladri Das · 2013
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.