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

3-SATHamiltonian cycleplanar graph

Mathematics Subject Classification ID

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

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

(12)

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

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)