Frozen development in graph coloring

DOI10.1016/S0304-3975(01)00164-5zbMath0983.68145MaRDI QIDQ5958809

Joseph C. Culberson, Ian Philip Gent

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

backbonegraph coloringspinefrozen developmentthreshold phenomena

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Super Solutions of Random Instances of Satisfiability ⋮ On the Integration of Singleton Consistencies and Look-Ahead Heuristics ⋮ Regular pattern-free coloring ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ A cooperative search method for the \(k\)-coloring problem ⋮ Computational complexity of auditing finite attributes in statistical databases ⋮ Towards backbone computing: A Greedy-Whitening based approach ⋮ The \(k\)-coloring fitness landscape ⋮ Constructive generation of very hard 3-colorability instances ⋮ Another look at graph coloring via propositional satisfiability ⋮ Graph coloring in the estimation of sparse derivative matrices: Instances and applications ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ A branch-and-cut algorithm for graph coloring ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ CsegGraph: a graph colouring instance generator ⋮ Coloring Random Graphs ⋮ A search space ``cartography for guiding graph coloring heuristics ⋮ Covering arrays on graphs ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ On the complexity of unfrozen problems ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ Spines of random constraint satisfaction problems: definition and connection with computational complexity ⋮ Fuzzy colouring of fuzzy graphs

Cites Work

• The hardest constraint problems: A double phase transition
• Experimental results on the crossover point in random 3-SAT
• The satisfiability constraint gap
• Locating the phase transition in binary constraint satisfaction problems
• Many hard examples for resolution
• The main properties of random graphs with a large number of vertices and edges
• Determining the Chromatic Number of a Graph
• Determining computational complexity from characteristic ‘phase transitions’
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item