Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT

DOI10.1016/j.dam.2008.09.011zbMath1186.68218OpenAlexW2100367658MaRDI 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

zbMATH Keywords

polynomial complexityNP-completeclausal graphnondeterministic polynomial complexityone-in-three SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

\(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments ⋮ On the complexity of multi-parameterized cluster editing ⋮ Clustering without replication in combinatorial circuits ⋮ Popular matchings with variable item copies

Cites Work

• A simplified NP-complete satisfiability problem
• Computational complexity of some restricted instances of 3-SAT
• TWO THEOREMS IN GRAPH THEORY
• Paths, Trees, and Flowers
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

This page was built for publication: Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT