Optimal Index Codes with Near-Extreme Rates

Details Optimal Index Codes with Near-Extreme Rates Optimal Index Codes with Near-Extreme Rates

2012-02-06

arxiv.org/abs/1202.1150v1

Computer Science

Information Theory

5 pages, submitted

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimal Index Codes with Near-Extreme Rates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Index Codes with Near-Extreme Rates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Index Codes with Near-Extreme Rates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-119578