Planar 3-SAT with a clause/variable cycle
From MaRDI portal
Publication:5116495
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)
Recommendations
- Planar 3-SAT with a clause/variable cycle
- On strongly planar 3SAT
- On strongly planar not-all-equal 3SAT
- scientific article; zbMATH DE number 152108
- scientific article; zbMATH DE number 1113997
- scientific article; zbMATH DE number 1954174
- 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
Cites work
- scientific article; zbMATH DE number 432759 (Why is no real title available?)
- scientific article; zbMATH DE number 4094812 (Why is no real title available?)
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- scientific article; zbMATH DE number 1256776 (Why is no real title available?)
- A left-first search algorithm for planar graphs
- A partial k-arboretum of graphs with bounded treewidth
- A simplified NP-complete satisfiability problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Classic Nintendo games are (computationally) hard
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Determining the thickness of graphs is NP-hard
- How to draw a planar graph on a grid
- Minimum-weight triangulation is NP-hard
- Nested satisfiability
- Noncrossing Subgraphs in Topological Layouts
- On Representatives of Subsets
- Optimal binary space partitions for segments in the plane
- Planar Formulae and Their Uses
- Satisfiability of co-nested formulas
- The Complexity of Planar Counting Problems
- The Problem of Compatible Representatives
- The complexity of counting in sparse, regular, and planar graphs
- The complexity of induced minors and related problems
Cited in
(8)- 3-Valued Circuit SAT for STE with Automatic Refinement
- Games, Puzzles and Treewidth
- Planar 3-SAT with a clause/variable cycle
- Vertex-to-point conflict-free chromatic guarding is NP-hard
- scientific article; zbMATH DE number 152108 (Why is no real title available?)
- On strongly planar 3SAT
- scientific article; zbMATH DE number 4094812 (Why is no real title available?)
- On the hull number on cycle convexity of graphs
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)
