Coloring Random and Semi-Random k-Colorable Graphs

DOI10.1006/JAGM.1995.1034MaRDI QIDQ4845849zbMATH OpenOpenAlexFDO

Authors Avrim Blum, Joel Spencer

Publication date 17 September 1995

Published in Journal of Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1006/jagm.1995.1034

zbMATH Keywords

random graphalgorithmsemi-random sourcespolynomial time coloring

Mathematics Subject Classification ID

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
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
• Online Predictions for Online TSP on the Line
• The simultaneous semi-random model for TSP
• Non-independent randomized rounding and coloring
• Bilu-Linial stability, certified algorithms and the independent set problem
• The simultaneous semi-random model for TSP
• A Simple SVD Algorithm for Finding Hidden Partitions
• 随机图的$f$-染色的分类 II
• PASS approximation: a framework for analyzing and designing heuristics
• Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
• Algorithms approaching the threshold for semi-random planted clique
• 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)