- Title
- A new class of index coding instances where linear coding is optimal
- Creator
- Ong, Lawrence
- Relation
- 2014 International Symposium on Network Coding (NetCod 2014). Proceedings of the 2014 International Symposium on Network Coding (Aalborg, Denmark 27-28 June, 2014)
- Publisher Link
- http://dx.doi.org/10.1109/NETCOD.2014.6892122
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2014
- Description
- 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.
- Subject
- bipartite graph; encoding; machine assisting indexing; network coding; receivers; upper bound
- Identifier
- http://hdl.handle.net/1959.13/1064767
- Identifier
- uon:17645
- Identifier
- ISBN:9781479962174
- Rights
- © 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.
- Language
- eng
- Full Text
- Reviewed
- Hits: 998
- Visitors: 1351
- Downloads: 388
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 339 KB | Adobe Acrobat PDF | View Details Download |