Publication:3002828
From MaRDI portal
DOI10.4086/toc.2011.v007a003zbMath1243.68183MaRDI QIDQ3002828
Shmuel Safra, Subhash A. Khot, Per Austrin
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2011.v007a003
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
On Constant Time Approximation of Parameters of Bounded Degree Graphs, New techniques for approximating optimal substructure problems in power-law graphs, Donation center location problem, Recoverable Values for Independent Sets, Vertex Cover in Graphs with Locally Few Colors, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses