2017/01/23 by Vijaya Kumar Mareedu, Prasad Krishnan, Mareedu, Vijaya Kumar +1
Computer Science · Engineering · #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1701.06273
openalex publication_date 2017/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The index coding problem is a problem of efficient broadcasting with side-information. We look at the uniprior index coding problem, in which the receivers have disjoint side-information symbols and arbitrary demand sets. Previous work has addressed single uniprior index coding, in which each receiver has a single unique side-information symbol. Modeling the uniprior index coding problem as a supergraph, we focus on a class of uniprior problems defined on generalized cycle supergraphs. For such problems, we prove upper and lower bounds on the optimal broadcast rate. Using a connection with Eulerian directed graphs, we also show that the upper and lower bounds are equal for a subclass of uniprior problems. We show the NP-hardness of finding the lower bound for uniprior problems on generalized cycles. Finally, we look at a simple extension of the generalized cycle uniprior class for which we give bounds on the optimal rate and show an explicit scheme which achieves the upper bound.