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

DOI10.1145/3183350zbMATH Open1414.68036OpenAlexW2792593888WikidataQ130112805 ScholiaQ130112805MaRDI QIDQ4577957FDOQ4577957

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

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

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)

Cites Work

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