Coloring sparse random graphs in polynomial average time

DOI10.1007/3-540-45253-2_38MaRDI QIDQ2753957zbMATH OpenFDO

Authors C. R. Subramanian

Publication date 11 November 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45253-2_38

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Mathematical Foundations of Computer Science 2005
• Algorithms for Colouring Random k-colourable Graphs
• Why almost all k-colorable graphs are easy to color
• Fast parallel algorithms for coloring random graphs
• A note on coloring sparse random graphs

Cited in

(4)

• Maximum Weight Partial Colorings on Sparse Random Graphs
• Average-case complexity of backtrack search for coloring sparse random graphs
• Colouring random graphs in expected polynomial time
• A Complexity Dichotomy for the Coloring of Sparse Graphs

This page was built for publication: Coloring sparse random graphs in polynomial average time

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