Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
From MaRDI portal
Publication:1028148
DOI10.1016/j.dam.2008.09.011zbMath1186.68218MaRDI QIDQ1028148
Stephen Foster, Richard T. Denman
Publication date: 30 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.09.011
polynomial complexity; NP-complete; clausal graph; nondeterministic polynomial complexity; one-in-three SAT
68Q25: Analysis of algorithms and problem complexity
Related Items
\(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments, Popular matchings with variable item copies, On the complexity of multi-parameterized cluster editing, Clustering without replication in combinatorial circuits
Cites Work