Kamal Jain
Abstract
Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, this conjecture could not so far be verified even for the simple network consisting of K 3, 2 with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network.
- {1} M. Adler, N. J. A. Harvey, K. Jain, R. D. Kleinberg, and A. R. Lehman, "On the capacity of information networks, "in Proc. SODA 2006, 2006. Google Scholar
- {2} R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow, " IEEE Trans. Inf. Theory, vol. 46, pp. 1204-1216, 2000. Google Scholar
- {3} M. Charikar and A. Argawal, "On the advantage of network coding for improving network throughput, "in Proc. 2004 IEEE Inf. Theory Workshop , San Antonio, TX, 2004.Google Scholar
- {4} N. J. A. Harvey, R. D. Kleinberg, and A. R. Lehman, "On the capacity of information networks, " IEEE Trans. Inf. Theory, vol. 52, no. 6, pp. 2345-2364, Jun. 2006. Google Scholar
- {5} T. Ho, R. Koetter, M. Médard, M. Effros, J. Shi, and D. Karger, "A random linear network coding approach to multicast," IEEE Trans. Inf. Theory, 2005, submitted for publication. Google Scholar
- {6} K. Jain, "Security based on network topology against the wiretapping attack, " IEEE Magazine, Special Issue on Topics in Wireless Security, 2004. Google Scholar
- {7} R. Koetter and M. Medard, "An algebraic approach to network coding," IEEE/ACM Trans. Netw.. Google Scholar
- {8} G. Kramer and S. A. Savari, "Progressive d -separating edge set bounds on network coding rates, "in Proc. IEEE Int. Symp. Information Theory, Adelaide, Australia, Sep. 2005, pp. 1588-1592.Google Scholar
- {9} Z. Li and B. Li, "Network coding in undirected networks, "in Proc. CISS, 2004.Google Scholar
- {10} F. T. Leighton and S. Rao, "An approximate max-flow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms, "in Proc. 29th Annu. IEEE Symp. Found. Comput. Sci., 1988, pp. 422-431.Google Scholar
- {11} D. Slepian and J. K. Wolf, "Noiseless coding of correlated information sources," IEEE Trans. Inf. Theory., vol. IT-19, pp. 471-480, Mar. 1973.Google Scholar
- {12} V. V. Vazirani, Approximation Algorithms. New york: Springer-Verlag, 2001. Google Scholar
Index Terms
- On the capacity of multiple unicast sessions in undirected graphs
Recommendations
Undirected simple connected graphs with minimum number of spanning trees
We show that for positive integers n, m with n(n-1)/2>=m>=n-1, the graph L"n","m having n vertices and m edges that consists of an (n-k)-clique and k-1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m ...
Multiple Coloring of Cone Graphs
A $k$-fold coloring of a graph assigns to each vertex a set of $k$ colors, and color sets assigned to adjacent vertices are disjoint. The $k$th chromatic number $\chi_k(G)$ of a graph $G$ is the minimum total number of colors needed in a $k$-fold ...
NP-hardness of multiple bondage in graphs
Let p 2 be a positive integer. The p -bondage number of a graph G is the minimum number of edges whose removal from G results in a graph with larger p -domination number. The p -total bondage number of a graph G with no isolated vertex is the minimum ...
Comments