Planar 3-SAT with a clause/variable cycle
From MaRDI portal
Publication:5116495
DOI10.4230/LIPIcs.SWAT.2018.31zbMath1477.68294OpenAlexW2949221776MaRDI QIDQ5116495
Publication date: 25 August 2020
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/8857/pdf/LIPIcs-SWAT-2018-31.pdf
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) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Eulerian and Hamiltonian graphs (05C45)
Related Items
Games, Puzzles and Treewidth, Vertex-to-point conflict-free chromatic guarding is NP-hard, On the hull number on cycle convexity of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nested satisfiability
- A simplified NP-complete satisfiability problem
- How to draw a planar graph on a grid
- Flip distance between triangulations of a simple polygon is NP-complete
- A partial k-arboretum of graphs with bounded treewidth
- Satisfiability of co-nested formulas
- The complexity of induced minors and related problems
- A left-first search algorithm for planar graphs
- Classic Nintendo games are (computationally) hard
- Counting truth assignments of formulas of bounded tree-width or clique-width
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Noncrossing Subgraphs in Topological Layouts
- Minimum-weight triangulation is NP-hard
- Planar Formulae and Their Uses
- Determining the thickness of graphs is NP-hard
- The Problem of Compatible Representatives
- The Complexity of Planar Counting Problems
- On Representatives of Subsets
- OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs