On percolation and ‐hardness
From MaRDI portal
Publication:4633317
DOI10.1002/rsa.20772zbMath1409.05181OpenAlexW2963244154MaRDI QIDQ4633317
Daniel Reichman, Huck Bennett, Igor Shinkar
Publication date: 2 May 2019
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20772
Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- Zero knowledge and the chromatic number
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Heuristics for semirandom graph problems
- On weighted vs unweighted versions of combinatorial optimization problems
- Percolation on finite graphs and isoperimetric inequalities.
- On the Bogolyubov-Ruzsa lemma
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Random sampling in cut, flow, and network design problems
- Improved Hardness of Approximating Chromatic Number
- The phase transition in random graphs: A simple proof
- Recoverable Values for Independent Sets
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Conditional Hardness for Approximate Coloring
- Smoothed analysis of algorithms
- On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
- Information, Physics, and Computation
- The greedy coloring is a bad probabilistic algorithm
- The Complexity of Near-Optimal Graph Coloring
- Percolation
- The emergence of a giant component in random subgraphs of pseudo-random graphs
- Reducibility among Combinatorial Problems
- Smoothed Analysis of Local Search for the Maximum-Cut Problem
- Probability and Computing
- Algorithms and Data Structures
- Packing, counting and covering Hamilton cycles in random directed graphs
This page was built for publication: On percolation and ‐hardness
