scientific article; zbMATH DE number 7053287
From MaRDI portal
Publication:5743408
zbMath1423.94034MaRDI QIDQ5743408
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095151
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Semidefinite programming (90C22) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Information theory (general) (94A15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- The sandwich theorem
- Orthogonal representations over finite fields and the chromatic number of graphs
- Near-optimal algorithms for unique games
- New approximation guarantee for chromatic number
- Conditional Hardness for Approximate Coloring
- On the power of unique 2-prover 1-round games
- On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
- 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 Index Coding Problem and Its Relation to Network Coding and Matroid Theory
- On the hardness of approximating the chromatic number
