A spectral technique for coloring random 3-colorable graphs (preliminary version)
From MaRDI portal
Publication:2817627
DOI10.1145/195058.195187zbMath1345.05022OpenAlexW2047472567MaRDI QIDQ2817627
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195187
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Colouring Non-sparse Random Intersection Graphs ⋮ Cryptographic hardness of random local functions. Survey ⋮ Mutual exclusion scheduling ⋮ Hardness results and spectral techniques for combinatorial problems on circulant graphs ⋮ Probabilistic analysis of local search and NP-completeness result for constraint satisfaction ⋮ Semidefinite programming and combinatorial optimization