Coloring Random and Semi-Random k-Colorable Graphs

DOI10.1006/jagm.1995.1034zbMath0834.05025OpenAlexW2088272899MaRDI QIDQ4845849

Avrim L. Blum, J. H. 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

zbMATH Keywords

algorithmrandom graphsemi-random sourcespolynomial time coloring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

Independent sets in semi-random hypergraphs ⋮ Smoothed analysis of binary search trees ⋮ The simultaneous semi-random model for TSP ⋮ Smoothed Analysis on Connected Graphs ⋮ Online Predictions for Online TSP on the Line ⋮ Beyond the worst case: semi-random complexity analysis of winner determination ⋮ Unnamed Item ⋮ A Simple SVD Algorithm for Finding Hidden Partitions ⋮ PASS approximation: a framework for analyzing and designing heuristics ⋮ Finding large cliques in sparse semi-random graphs by simple randomized search heuristics ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ Unnamed Item ⋮ On the tractability of coloring semirandom graphs ⋮ Unnamed Item ⋮ Heuristics for semirandom graph problems ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs

This page was built for publication: Coloring Random and Semi-Random k-Colorable Graphs