scientific article; zbMATH DE number 5004842

zbMATH Open1102.05058MaRDI QIDQ3370783FDOQ3370783

R. Monasson

Publication date: 8 February 2006

Title of this publication is not available (Why is that?)

Recommendations

• Principles and Practice of Constraint Programming – CP 2004
• A theoretical analysis of backtracking in the graph coloring problem
• Average-case complexity of backtrack search for coloring sparse random graphs
• scientific article; zbMATH DE number 1984543
• scientific article; zbMATH DE number 1962838
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• On the tractability of coloring semirandom graphs
• Algorithms for Colouring Random k-colourable Graphs
• On backbone coloring of graphs
• Randomized algorithms for colourings of hypergraphs

zbMATH Keywords

graph coloringrandom graphsnonequilibrium statistical physicsbacktrack search algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms (68W40) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Stochastic methods (Fokker-Planck, Langevin, etc.) applied to problems in time-dependent statistical mechanics (82C31)

Cited In (7)

• Average-case complexity of backtrack search for coloring sparse random graphs
• The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
• Title not available (Why is that?)
• A theoretical analysis of backtracking in the graph coloring problem
• Complexity of Coloring Random Graphs
• Statistical physics analysis of the backtrack resolution of random 3-SAT instances

This page was built for publication:

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