Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques
- 1 February 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (6) , 3692-3711
Abstract
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 nonlinear 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.Keywords
All Related Versions
Funding Information
- Australian Research Council (FT110100195, FT140100219, DP150100903)
This publication has 22 references indexed in Scilit:
- On critical index coding problems2015
- Structural properties of index coding capacity using fractional graph theory2015
- Index Coding—An Interference Alignment PerspectiveIEEE Transactions on Information Theory, 2014
- Local time sharing for index coding2014
- Graph theory versus minimum rank for index coding2014
- Topological Interference Management Through Index CodingIEEE Transactions on Information Theory, 2013
- Dynamic Index Coding for Wireless Broadcast NetworksIEEE Transactions on Information Theory, 2013
- General index coding with side information: Three decoder case2013
- Local graph coloring and index coding2013
- On the complementary Index Coding problem2011