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

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

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

(7)

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

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)