Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/102539
Title: Optimal index codes with near-extreme rates
Authors: Dau, Son Hoang
Skachek, Vitaly
Chee, Yeow Meng
Keywords: DRNTU::Science::Mathematics
Issue Date: 2012
Source: Dau, S. H., Skachek, V., & Chee, Y. M. (2012). Optimal index codes with near-extreme rates. 2012 IEEE International Symposium on Information Theory - ISIT, pp.2241-2245.
Abstract: The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. It is also shown that the decision problem of whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time.
URI: https://hdl.handle.net/10356/102539
http://hdl.handle.net/10220/16391
DOI: 10.1109/ISIT.2012.6283852
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Conference Papers

SCOPUSTM   
Citations 50

5
Updated on Jan 27, 2023

Page view(s) 50

454
Updated on Feb 6, 2023

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.