Average-case complexity of backtrack search for coloring sparse random graphs (Q394742): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2013.06.003
+Normal rank
@@ Property / OpenAlex ID @@
+W2051236701
@@ Property / OpenAlex ID: W2051236701 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3286850
@@ Property / cites work: Q3286850 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2743189
@@ Property / cites work: Q2743189 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4519896
@@ Property / cites work: Q4519896 / rank @@
+Normal rank
@@ Property / cites work @@
+The concentration of the chromatic number of random graphs
+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 @@
+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 @@
+Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
+Normal rank
@@ Property / cites work @@
+The two possible values of the chromatic number of a random graph
+Normal rank
@@ Property / cites work @@
+Backtrack: An O(1) expected time algorithm for the graph coloring problem
+Normal rank
@@ Property / cites work @@
+A theoretical analysis of backtracking in the graph coloring problem
+Normal rank
@@ Property / cites work @@
+Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / 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 @@
+Zero knowledge and the chromatic number
@@ Property / cites work: Zero knowledge and the chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002782
@@ Property / cites work: Q3002782 / rank @@
+Normal rank
@@ Property / cites work @@
+Chromatic Scheduling and the Chromatic Number Problem
+Normal rank
@@ Property / cites work @@
+Q5670645
@@ Property / cites work: Q5670645 / rank @@
+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 @@
+Q4012216
@@ Property / cites work: Q4012216 / 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 @@
+The hardest constraint problems: A double phase transition
+Normal rank
@@ Property / cites work @@
+Refining the phase transition in combinatorial search
+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 @@
+Q3370783
@@ Property / cites work: Q3370783 / rank @@
+Normal rank
@@ Property / cites work @@
+Why almost all \(k\)-colorable graphs are easy to color
+Normal rank
@@ Property / cites work @@
+Principles and Practice of Constraint Programming – CP 2004
+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 @@
+Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
+Normal rank
@@ Property / cites work @@
+Q5187324
@@ Property / cites work: Q5187324 / rank @@
+Normal rank
@@ Property / cites work @@
+Almost all graphs with average degree 4 are 3-colorable
+Normal rank
@@ Property / cites work @@
+On-Line Coloring of Sparse Random Graphs and Random Trees
+Normal rank
@@ Property / cites work @@
+Exact and approximative algorithms for coloring G(n,p)
+Normal rank
@@ Property / cites work @@
+A note on coloring sparse random graphs
@@ Property / cites work: A note on coloring sparse random graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Q3090774
@@ Property / cites work: Q3090774 / rank @@
+Normal rank