Loading...
| Friend's email | |
| Your name | |
| Your email | |
| enter code | |
This page was sent successfuly
- Type of Document: Article
- DOI: 10.1109/ISIT.2014.6874839
- Abstract:
- In this paper we define critical graphs as minimal graphs that support a given set of rates for the index coding problem, and study them for both the one-shot and asymptotic setups. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. In addition, we show that the capacity region of the index coding associated with a given graph can be obtained by time-sharing over valid index codes for its strongly connected components
- Keywords:
- Graph theory ; Capacity regions ; Critical graph ; Index coding ; Nonlinear index ; Strongly connected ; Strongly connected component ; Time-sharing ; Codes (symbols)
- Source: IEEE International Symposium on Information Theory - Proceedings ; 2014 , p. 281-285
- URL: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6874839&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel7%2F6867217%2F6874773%2F06874839.pdf%3Farnumber%3D6874839