On finding randomly planted cliques in arbitrary graphs
From MaRDI portal
Cites work
- A better approximation ratio for the vertex cover problem
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A New Algorithm for the Robust Semi-random Independent Set Problem
- A still better performance guarantee for approximate graph coloring
- Algorithms approaching the threshold for semi-random planted clique
- Approximate graph coloring by semidefinite programming
- Approximating Maximum Clique by Removing Subgraphs
- Approximating maximum independent sets by excluding subgraphs
- Approximating the independence number via the -function
- Concentration of Measure for the Analysis of Randomized Algorithms
- Expected complexity of graph partitioning problems
- Finding a Maximum Independent Set in a Sparse Random Graph
- Finding and certifying a large hidden clique in a semirandom graph
- Finding Large Independent Sets in Polynomial Expected Time
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Heuristics for semirandom graph problems
- scientific article; zbMATH DE number 1256685 (Why is no real title available?)
- scientific article; zbMATH DE number 1380608 (Why is no real title available?)
- scientific article; zbMATH DE number 5686753 (Why is no real title available?)
- Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Introduction to algorithms.
- Introduction to Semirandom Models
- Large Cliques Elude the Metropolis Process
- Learning from untrusted data
- Linear degree extractors and the inapproximability of max clique and chromatic number
- New tools for graph coloring
- On finding balanced bicliques via matchings
- On the effect of randomness on planted 3-coloring models
- Optimal Long Code Test with One Free Bit
- Reducibility among combinatorial problems
- Statistical algorithms and a lower bound for detecting planted cliques
- The NP-completeness column: An ongoing guide
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
This page was built for publication: On finding randomly planted cliques in arbitrary graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346839)
