On percolation and ‐hardness (Q4633317): Difference between revisions

@@ Property / DOI @@
-.1002/rsa.20772
@@ Property / DOI: 10.1002/rsa.20772 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1002/rsa.20772
@@ Property / full work available at URL: https://doi.org/10.1002/rsa.20772 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2963244154
@@ Property / OpenAlex ID: W2963244154 / rank @@
+Normal rank
@@ Property / cites work @@
+Percolation on finite graphs and isoperimetric inequalities.
+Normal rank
@@ Property / cites work @@
+Q2784326
@@ Property / cites work: Q2784326 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
+Normal rank
@@ Property / cites work @@
+Q5365060
@@ Property / cites work: Q5365060 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228453
@@ Property / cites work: Q4228453 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5782525
@@ Property / cites work: Q5782525 / rank @@
+Normal rank
@@ Property / cites work @@
+On weighted vs unweighted versions of combinatorial optimization problems
+Normal rank
@@ Property / cites work @@
+Conditional Hardness for Approximate Coloring
@@ Property / cites work: Conditional Hardness for Approximate Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimum vertex cover
+Normal rank
@@ Property / cites work @@
+On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
+Normal rank
@@ Property / cites work @@
+Q3286850
@@ Property / cites work: Q3286850 / rank @@
+Normal rank
@@ Property / cites work @@
+Smoothed Analysis of Local Search for the Maximum-Cut Problem
+Normal rank
@@ Property / cites work @@
+Zero knowledge and the chromatic number
@@ Property / cites work: Zero knowledge and the chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+Heuristics for semirandom graph problems
@@ Property / cites work: Heuristics for semirandom graph problems / rank @@
+Normal rank
@@ Property / cites work @@
+Recoverable Values for Independent Sets
@@ Property / cites work: Recoverable Values for Independent Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Packing, counting and covering Hamilton cycles in random directed graphs
+Normal rank
@@ Property / cites work @@
+The emergence of a giant component in random subgraphs of pseudo-random graphs
+Normal rank
@@ Property / cites work @@
+Q3122905
@@ Property / cites work: Q3122905 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Near-Optimal Graph Coloring
@@ Property / cites work: The Complexity of Near-Optimal Graph Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Percolation
@@ Property / cites work: Percolation / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Hardness of Approximating Chromatic Number
+Normal rank
@@ Property / cites work @@
+Random sampling in cut, flow, and network design problems
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+The phase transition in random graphs: A simple proof
+Normal rank
@@ Property / cites work @@
+The greedy coloring is a bad probabilistic algorithm
+Normal rank
@@ Property / cites work @@
+Information, Physics, and Computation
@@ Property / cites work: Information, Physics, and Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Probability and Computing
@@ Property / cites work: Probability and Computing / rank @@
+Normal rank
@@ Property / cites work @@
+Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
+Normal rank
@@ Property / cites work @@
+On the Bogolyubov-Ruzsa lemma
@@ Property / cites work: On the Bogolyubov-Ruzsa lemma / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms and Data Structures
@@ Property / cites work: Algorithms and Data Structures / rank @@
+Normal rank
@@ Property / cites work @@
+Smoothed analysis of algorithms
@@ Property / cites work: Smoothed analysis of algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for metric facility location and             <i>k</i>             -Median problems using the primal-dual schema and Lagrangian relaxation
+Normal rank
@@ Property / DOI @@
+.1002/RSA.20772
@@ Property / DOI: 10.1002/RSA.20772 / rank @@
+Normal rank