Efficient Algorithms for Minrank and Index Coding for Low-Treewidth GraphsResearch Paper
The minrank of a graph was introduced by Haemers as an upper bound on the Shannon capacity. Its main motivation today is index coding: a sender broadcasts a string to receivers, receiver wants and already knows the coordinates indexed by its out-neighbours in a knowledge graph , and the question is how short the broadcast can…