Complexity of coloring random graphs: an experimental study of the hardest region

DOI10.1145/3183350MaRDI QIDQ4577957zbMATH OpenOpenAlexWikidataFDO

Authors Zoltán Ádám Mann

Publication date 6 August 2018

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3183350

zbMATH Keywords

phase transitiongraph coloringrandom graphsaverage-case complexitybacktrack search

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Why almost all \(k\)-colorable graphs are easy to color
• Why Almost All k-Colorable Graphs Are Easy
• Coloring random graphs
• Average-case complexity of backtrack search for coloring sparse random graphs
• A theoretical analysis of backtracking in the graph coloring problem

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 5004842 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3895112 (Why is no real title available?)
• scientific article; zbMATH DE number 3404264 (Why is no real title available?)
• A note on the chromatic number of a dense random graph
• A note on the sharp concentration of the chromatic number of random graphs
• A theoretical analysis of backtracking in the graph coloring problem
• Almost all graphs with average degree 4 are 3-colorable
• Almost all k-colorable graphs are easy to color
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Average-case complexity of backtrack search for coloring sparse random graphs
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Chromatic Scheduling and the Chromatic Number Problem
• Determining computational complexity from characteristic ``phase transitions
• Finding the chromatic number by means of critical graphs
• Frozen development in graph coloring
• Generating hard satisfiability problems
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• How Sharp is the Concentration of the Chromatic Number?
• Linear degree extractors and the inapproximability of max clique and chromatic number
• New methods to color the vertices of a graph
• On colouring random graphs
• Principles and Practice of Constraint Programming – CP 2004
• Reducibility among combinatorial problems
• Refining the phase transition in combinatorial search
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Statistical physics analysis of the backtrack resolution of random 3-SAT instances
• The Complexity of Near-Optimal Graph Coloring
• The chromatic number of random graphs
• The chromatic number of random graphs
• The concentration of the chromatic number of random graphs
• The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
• The freezing threshold for \(k\)-colourings of a random graph
• The hardest constraint problems: A double phase transition
• The two possible values of the chromatic number of a random graph
• Zero knowledge and the chromatic number

This page was built for publication: Complexity of coloring random graphs: an experimental study of the hardest region

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