The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic

DOI10.1088/0305-4470/36/43/027zbMATH Open1072.05575arXivcond-mat/0304606OpenAlexW3106065224MaRDI QIDQ5696396FDOQ5696396

Authors: Liat Ein-Dor, R. Monasson 

Publication date: 18 October 2005

Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Abstract: We study the dynamics of a backtracking procedure capable of proving uncolourability of graphs, and calculate its average running time T for sparse random graphs, as a function of the average degree c and the number of vertices N. The analysis is carried out by mapping the history of the search process onto an out-of-equilibrium (multi-dimensional) surface growth problem. The growth exponent of the average running time is quantitatively predicted, in agreement with simulations.

Full work available at URL: https://arxiv.org/abs/cond-mat/0304606

Recommendations

• Principles and Practice of Constraint Programming – CP 2004
• Average-case complexity of backtrack search for coloring sparse random graphs
• A theoretical analysis of backtracking in the graph coloring problem
• scientific article
• Coloring random graphs

zbMATH Keywords

surface growthuncolourabilitybacktracking produce

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cited In (5)

• Average-case complexity of backtrack search for coloring sparse random graphs
• Principles and Practice of Constraint Programming – CP 2004
• Complexity of coloring random graphs: an experimental study of the hardest region
• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
• The resolution complexity of random graph \(k\)-colorability

This page was built for publication: The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic

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