Planar 3-SAT with a clause/variable cycle

MaRDI QIDQ5226839zbMATH OpenFDO

Authors Alexander Pilz

Publication date 1 August 2019

Full work available at URL https://arxiv.org/abs/1710.07476, https://dmtcs.episciences.org/5521/pdf

zbMATH Keywords

Hamiltonian cycleplanar graph3-SAT

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• Planar 3-SAT with a clause/variable cycle
• scientific article; zbMATH DE number 152108
• The Complexity of Planar Counting Problems
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• scientific article; zbMATH DE number 4094812

Cited in

(9)

• Planar 3-SAT with a clause/variable cycle
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• Positive planar satisfiability problems under 3-connectivity constraints
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• scientific article; zbMATH DE number 152108 (Why is no real title available?)
• Colourful components in \(k\)-caterpillars and planar graphs
• 3-Valued Circuit SAT for STE with Automatic Refinement
• On conflict-free spanning tree: algorithms and complexity

This page was built for publication: Planar 3-SAT with a clause/variable cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226839)