A Bound on the Shannon Capacity via a Linear Programming Variation

04/16/2018
by   Sihuang Hu, et al.
0

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ász 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset