A Bound on the Shannon Capacity via a Linear Programming Variation

DOI10.1137/17M115565XzbMath1423.05124arXiv1804.05529OpenAlexW3099089427WikidataQ129282069 ScholiaQ129282069MaRDI QIDQ4584958

Sihuang Hu, Itzhak Tamo, Ofer Shayevitz

Publication date: 5 September 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.05529

zbMATH Keywords

linear programmingShannon capacityindex coding

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fractional graph theory, fuzzy graph theory (05C72)

Related Items (5)

Shannon capacity and the categorical product ⋮ The zero-error capacity of binary channels with 2-memories ⋮ Approximation of the Shannon capacity via matrix cone programming ⋮ Probabilistic refinement of the asymptotic spectrum of graphs ⋮ Topological bounds on the dimension of orthogonal representations of graphs

Uses Software

• SageMath

Cites Work

• Unnamed Item
• Unnamed Item
• The sandwich theorem
• Local chromatic number and Sperner capacity
• On the Shannon capacity of a graph
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• Nonlinear Index Coding Outperforming the Linear Optimum
• Index Coding With Side Information
• Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
• On a Problem of C. E. Shannon in Graph Theory

This page was built for publication: A Bound on the Shannon Capacity via a Linear Programming Variation