Average-case complexity of backtrack search for coloring sparse random graphs

DOI10.1016/j.jcss.2013.06.003zbMath1410.68173MaRDI QIDQ394742

Anikó Szajkó, Zoltán Ádám Mann

Publication date: 27 January 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2013.06.003

zbMATH Keywords

graph coloring; random graphs; average-case complexity; search tree; backtrack

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C80: Random graphs (graph-theoretic aspects)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Complexity of Coloring Random Graphs, Uncertain vertex coloring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Why almost all \(k\)-colorable graphs are easy to color
• A note on coloring sparse random graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• A note on the sharp concentration of the chromatic number of random graphs
• Zero knowledge and the chromatic number
• The concentration of the chromatic number of random graphs
• The hardest constraint problems: A double phase transition
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• Refining the phase transition in combinatorial search
• On-Line Coloring of Sparse Random Graphs and Random Trees
• 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
• On colouring random graphs
• The Complexity of Near-Optimal Graph Coloring
• New methods to color the vertices of a graph
• Exact and approximative algorithms for coloring G(n,p)
• Reducibility among Combinatorial Problems
• Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Chromatic Scheduling and the Chromatic Number Problem
• 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
• The chromatic number of random graphs
• The chromatic number of random graphs
• Almost all graphs with average degree 4 are 3-colorable
• Frozen development in graph coloring