dc.contributor.authorDau, Son Hoang
dc.contributor.authorSkachek, Vitaly
dc.contributor.authorChee, Yeow Meng
dc.date.accessioned2013-10-10T06:09:26Z
dc.date.available2013-10-10T06:09:26Z
dc.date.copyright2012en_US
dc.date.issued2012
dc.identifier.citationDau, 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.
dc.identifier.urihttp://hdl.handle.net/10220/16391
dc.description.abstractThe 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.en_US
dc.language.isoenen_US
dc.subjectDRNTU::Science::Mathematics
dc.titleOptimal index codes with near-extreme ratesen_US
dc.typeConference Paper
dc.contributor.conferenceIEEE International Symposium on Information Theory (2012 : Cambridge, US)en_US
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen_US
dc.identifier.doihttp://dx.doi.org/10.1109/ISIT.2012.6283852


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record