On the complexity of unfrozen problems
From MaRDI portal
Publication:2581544
DOI10.1016/j.dam.2005.05.003zbMath1085.68065MaRDI QIDQ2581544
Adam Beacham, Joseph C. 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
NP-completeness; Hamiltonian cycle; Satisfiability; Graph coloring; Subgraph isomorphism; Frozen complexity
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Complexity of Stability., Gap theorems for robust satisfiability: Boolean CSPs and beyond, Complexity of stability, DP-Complete Problems Derived from Extremal NP-Complete Properties
Uses Software
Cites Work