A Bound on the Shannon Capacity via a Linear Programming Variation
classification
💻 cs.IT
math.COmath.IT
keywords
boundcapacitylinearprogrammingshannonuppervariationbroadcast
read the original abstract
We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lov\'asz theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of Index Coding.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.