Coloring Random and Semi-Random k-Colorable Graphs
From MaRDI portal
Publication:4845849
DOI10.1006/JAGM.1995.1034zbMATH Open0834.05025OpenAlexW2088272899MaRDI QIDQ4845849FDOQ4845849
Authors: Avrim Blum, Joel Spencer 
Publication date: 17 September 1995
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1995.1034
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cited In (21)
- Independent sets in semi-random hypergraphs
- Smoothed Analysis on Connected Graphs
- Why almost all \(k\)-colorable graphs are easy to color
- On the tractability of coloring semirandom graphs
- Heuristics for semirandom graph problems
- New abilities and limitations of spectral graph bisection
- Smoothed analysis of binary search trees
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Title not available (Why is that?)
- Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
- The simultaneous semi-random model for TSP
- Online Predictions for Online TSP on the Line
- Bilu-Linial stability, certified algorithms and the independent set problem
- Non-independent randomized rounding and coloring
- A Simple SVD Algorithm for Finding Hidden Partitions
- The simultaneous semi-random model for TSP
- 随机图的$f$-染色的分类 II
- Algorithms approaching the threshold for semi-random planted clique
- Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
- PASS approximation: a framework for analyzing and designing heuristics
- Beyond the worst case: semi-random complexity analysis of winner determination
This page was built for publication: Coloring Random and Semi-Random k-Colorable Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4845849)
