On the complexity of unfrozen problems
DOI10.1016/J.DAM.2005.05.003zbMATH Open1085.68065OpenAlexW2156111468MaRDI QIDQ2581544FDOQ2581544
Authors: Adam Beacham, J. Culberson 
Publication date: 10 January 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.003
Recommendations
- Recognizing frozen variables in constraint satisfaction problems
- scientific article; zbMATH DE number 67483
- Frozen variables in random Boolean constraint satisfaction problems
- Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete
- DP-Complete Problems Derived from Extremal NP-Complete Properties
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Theory and Probability
- Title not available (Why is that?)
- Title not available (Why is that?)
- Frozen development in graph coloring
- Title not available (Why is that?)
- Title not available (Why is that?)
- Determining computational complexity from characteristic ``phase transitions
- Generating hard satisfiability problems
- The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
- Title not available (Why is that?)
Cited In (6)
- Recognizing frozen variables in constraint satisfaction problems
- Complexity of stability
- DP-Complete Problems Derived from Extremal NP-Complete Properties
- Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete
- Complexity of Stability.
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
Uses Software
This page was built for publication: On the complexity of unfrozen problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581544)
