Linear Index Coding via Semidefinite Programming
From MaRDI portal
Publication:5410256
DOI10.1017/S0963548313000564zbMath1287.94024arXiv1107.1958MaRDI QIDQ5410256
Publication date: 16 April 2014
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.1958
Semidefinite programming (90C22) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Information theory (general) (94A15)
Related Items (7)
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The minrank of random graphs ⋮ Unnamed Item ⋮ Topological bounds on the dimension of orthogonal representations of graphs
Cites Work
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Orthogonal representations over finite fields and the chromatic number of graphs
- Conditional Hardness for Approximate Coloring
- Improving the performance guarantee for approximate graph coloring
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
- New approximation algorithms for graph coloring
- Network information flow
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Distributed source coding for satellite communications
- Coloring -colorable graphs using relatively small palettes
- Nonlinear Index Coding Outperforming the Linear Optimum
- Index Coding With Side Information
- On the Hardness of Approximating the Network Coding Capacity
- On the hardness of approximating the chromatic number
This page was built for publication: Linear Index Coding via Semidefinite Programming
