.png){kind=icon}
.png){kind=icon}
Return
Critical Graphs in Index Coding
.png){kind=icon}
OA
AI
DOI：10.1109/JSAC.2014.2384294.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 nonlinear index coding, each critical graph is a union of disjoint strongly connected subgraphs. On the other hand, we identify a non-USCS critical graph for a one-shot nonlinear index coding problem. Next, we identify a few graph structures that are critical. In addition, we show that the capacity region of the index coding is additive for union of disjoint graphs.
Keywords:
Index coding
critical graphs
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
17.2
Papers:
6.4K
Citations:
3.1W