Technical Program

Paper Detail

Paper Title Optimal Index Codes for Some Interlinked Cycle Structures with Outer Cycles
Paper IdentifierTH4.R2.2
Authors Shanuja Sasi, B. Sundar Rajan, Indian Institute of Science, India
Session Index and Network Coding
Location Saint Germain, Level 3
Session Time Thursday, 11 July, 16:40 - 18:00
Presentation Time Thursday, 11 July, 17:00 - 17:20
Manuscript  Click here to download the manuscript
Abstract For index coding problems with special structure on the side-information graphs called Interlinked Cycle (IC) structures index codes have been proposed in the literature (C. Thapa, L. Ong, and S. Johnson, ``Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", in \textit{IEEE Trans. Inf. Theory, vol. 63, no. 6, Jun. 2017} with a correction in ``Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", in arxiv (arxiv:1603.00092v2 [cs.IT] 25 Feb 2018)). In this paper we consider a generalization of IC structures called {\it IC structures with interlocked outer cycles}. For IC structures with interlocked outer cycles we show that the optimal length (also known as the minrank of the index coding problem) depends on the maximum number of disjoint outer cycles. We give two sufficient conditions such that if any of these is satisfied then we provide explicit optimal index code construction. The conditions mentioned above are shown to be not necessary by an explicit example.