Planar 3-SAT with a clause/variable cycle

DOI10.4230/LIPICS.SWAT.2018.31zbMATH Open1477.68294OpenAlexW2949221776MaRDI QIDQ5116495FDOQ5116495

Alexander Pilz

Publication date: 25 August 2020

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/8857/pdf/LIPIcs-SWAT-2018-31.pdf

zbMATH Keywords

planar graph3-SAT1-in-3-SAT

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• A partial k-arboretum of graphs with bounded treewidth
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Minimum-weight triangulation is NP-hard
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• A simplified NP-complete satisfiability problem
• On Representatives of Subsets
• Nested satisfiability
• How to draw a planar graph on a grid
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of counting in sparse, regular, and planar graphs
• Title not available (Why is that?)
• The complexity of induced minors and related problems
• Title not available (Why is that?)
• Satisfiability of co-nested formulas
• A left-first search algorithm for planar graphs
• The Complexity of Planar Counting Problems
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• Noncrossing Subgraphs in Topological Layouts
• Determining the thickness of graphs is NP-hard
• Flip distance between triangulations of a simple polygon is NP-complete
• Classic Nintendo games are (computationally) hard

Cited In (5)

• Games, Puzzles and Treewidth
• Vertex-to-point conflict-free chromatic guarding is NP-hard
• Title not available (Why is that?)
• On the hull number on cycle convexity of graphs
• 3-Valued Circuit SAT for STE with Automatic Refinement

   Recommendations

• Title not available (Why is that?) 👍 👎
• On strongly planar 3SAT 👍 👎
• On strongly planar not-all-equal 3SAT 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Positive planar satisfiability problems under 3-connectivity constraints 👍 👎
• On the satisfiability threshold of formulas with three literals per clause 👍 👎
• Computational complexity of some restricted instances of 3-SAT 👍 👎
• On Planar Boolean CSP 👍 👎

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 Q5116495)