Open Research Newcastle
Browse

A new class of index coding instances where linear coding is optimal

Download (339.68 kB)
conference contribution
posted on 2025-05-10, 10:21 authored by Lawrence OngLawrence Ong
We study index-coding problems (one sender broadcasting messages to multiple receivers) where each message is requested by one receiver, and each receiver may know some messages a priori. This type of index-coding problems can be fully described by directed graphs. The aim is to find the minimum codelength that the sender needs to transmit in order to simultaneously satisfy all receivers' requests. For any directed graph, we show that if a maximum acyclic induced subgraph (MAIS) is obtained by removing two or fewer vertices from the graph, then the minimum codelength (i.e., the solution to the index-coding problem) equals the number of vertices in the MAIS, and linear codes are optimal for this index-coding problem. Our result increases the set of index-coding problems for which linear index codes are proven to be optimal.

History

Source title

Proceedings of the 2014 International Symposium on Network Coding

Name of conference

2014 International Symposium on Network Coding (NetCod 2014)

Location

Aalborg, Denmark

Start date

2014-06-27

End date

2014-06-28

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Place published

Piscataway, NJ

Language

  • en, English

College/Research Centre

Faculty of Engineering and Built Environment

School

School of Electrical Engineering and Computer Science

Rights statement

© 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Usage metrics

    Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC