Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate

Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova

Motivated by applications in distributed storage, the storage capacity of a graph was recently defined to be the maximum amount of information that can be stored across the vertice…