Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 63, Issue 6, Pages 3692-3711Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2017.2662706
Keywords
Index coding; interlinked-cycle cover; graph theory; broadcast with side information
Funding
- Australian Research Council [FT110100195,, FT140100219, DP150100903]
- Australian Research Council [FT140100219, FT110100195] Funding Source: Australian Research Council
Ask authors/readers for more resources
We consider a graphical approach to index coding. As cycles have been shown to provide coding gain, cycles and cliques (a specific type of overlapping cycles) have been exploited in an existing literature. In this paper, we define a more general form of overlapping cycles, called the interlinked-cycle (IC) structure, that generalizes cycles and cliques. We propose a scheme, called the interlinked-cycle-cover (ICC) scheme, that leverages IC structures in digraphs to construct scalar linear index codes. We characterize a class of infinitely many digraphs where our proposed scheme is optimal over all linear and non-linear index codes. Consequently, for this class of digraphs, we indirectly prove that scalar linear index codes are optimal. Furthermore, we show that the ICC scheme can outperform all the existing graph-based schemes (including partial-clique-cover and fractional-local-chromatic number schemes), and a random-coding scheme (namely, composite coding) for certain graphs.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available