2018/01/01 by Sihuang Hu, Itzhak Tamo, Ofer Shayevitz · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Error Correcting Code Techniques
paper · doi:10.1137/17m115565x
openalex created_date 2017/08/17 · openalex publication_date 2018/01/01 · openalex updated_date 2026/07/28
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.