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