Complexity of Coloring Random Graphs (Q4577957): Difference between revisions

@@ Property / cites work @@
+Almost all graphs with average degree 4 are 3-colorable
+Normal rank
@@ Property / cites work @@
+The two possible values of the chromatic number of a random graph
+Normal rank
@@ Property / cites work @@
+The concentration of the chromatic number of random graphs
+Normal rank
@@ Property / cites work @@
+A theoretical analysis of backtracking in the graph coloring problem
+Normal rank
@@ Property / cites work @@
+The chromatic number of random graphs
@@ Property / cites work: The chromatic number of random graphs / rank @@
+Normal rank
@@ Property / cites work @@
+How Sharp is the Concentration of the Chromatic Number?
+Normal rank
@@ Property / cites work @@
+New methods to color the vertices of a graph
@@ Property / cites work: New methods to color the vertices of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Chromatic Scheduling and the Chromatic Number Problem
+Normal rank
@@ Property / cites work @@
+Q4012216
@@ Property / cites work: Q4012216 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2741512
@@ Property / cites work: Q2741512 / rank @@
+Normal rank
@@ Property / cites work @@
+Frozen development in graph coloring
@@ Property / cites work: Frozen development in graph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Q5187324
@@ Property / cites work: Q5187324 / rank @@
+Normal rank
@@ Property / cites work @@
+The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
+Normal rank
@@ Property / cites work @@
+Q3286850
@@ Property / cites work: Q3286850 / rank @@
+Normal rank
@@ Property / cites work @@
+Zero knowledge and the chromatic number
@@ Property / cites work: Zero knowledge and the chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Near-Optimal Graph Coloring
@@ Property / cites work: The Complexity of Near-Optimal Graph Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+On colouring random graphs
@@ Property / cites work: On colouring random graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Finding the chromatic number by means of critical graphs
+Normal rank
@@ Property / cites work @@
+Refining the phase transition in combinatorial search
+Normal rank
@@ Property / cites work @@
+The hardest constraint problems: A double phase transition
+Normal rank
@@ Property / cites work @@
+Principles and Practice of Constraint Programming – CP 2004
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+The chromatic number of random graphs
@@ Property / cites work: The chromatic number of random graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A note on the sharp concentration of the chromatic number of random graphs
+Normal rank
@@ Property / cites work @@
+Average-case complexity of backtrack search for coloring sparse random graphs
+Normal rank
@@ Property / cites work @@
+Q5670645
@@ Property / cites work: Q5670645 / rank @@
+Normal rank
@@ Property / cites work @@
+The freezing threshold for k-colourings of a random graph
+Normal rank
@@ Property / cites work @@
+Q3370783
@@ Property / cites work: Q3370783 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Determining computational complexity from characteristic ‘phase transitions’
+Normal rank
@@ Property / cites work @@
+A note on the chromatic number of a dense random graph
+Normal rank
@@ Property / cites work @@
+Generating hard satisfiability problems
@@ Property / cites work: Generating hard satisfiability problems / rank @@
+Normal rank
@@ Property / cites work @@
+Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
+Normal rank
@@ Property / cites work @@
+Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
+Normal rank
@@ Property / cites work @@
+Almost all k-colorable graphs are easy to color
@@ Property / cites work: Almost all k-colorable graphs are easy to color / rank @@
+Normal rank
@@ Property / cites work @@
+Backtrack: An O(1) expected time algorithm for the graph coloring problem
+Normal rank
@@ Property / cites work @@
+Q3002782
@@ Property / cites work: Q3002782 / rank @@
+Normal rank