Semirandom models as benchmarks for coloring algorithms

DOI10.1137/1.9781611972962.4MaRDI QIDQ5233148zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Dan Vilenchik

Publication date 16 September 2019

Published in 2006 Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611972962.4

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Automata, Languages and Programming
• Colouring Semirandom Graphs
• Heuristics for semirandom graph problems
• Coloring random graphs
• Minimum Coloring k-Colorable Graphs in Polynomial Average Time

Cited in

(6)

• Colouring Semirandom Graphs
• The replica symmetric phase of random constraint satisfaction problems
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• On the tractability of coloring semirandom graphs
• Automata, Languages and Programming
• Heuristics for semirandom graph problems

This page was built for publication: Semirandom models as benchmarks for coloring algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233148)