Linear planar 3-SAT

DOI10.1016/J.TCS.2026.115834MaRDI QIDQ6837844zbMATH OpenFDO

Authors Victorien Desbois, Ocan Sankur, François Schwarzentruber

Publication date 26 March 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115834

zbMATH Keywords

complexity theorylinear 3-SATplanar 3-SATplanar graphsplanning

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A course in combinatorics.
• A simplified NP-complete satisfiability problem
• Efficient Planarity Testing
• Finding the intersection of two convex polyhedra
• Games, puzzles, and computation
• scientific article; zbMATH DE number 4060744 (Why is no real title available?)
• scientific article; zbMATH DE number 7788443 (Why is no real title available?)
• On the complexity of reconfiguration problems
• On the history of the Euclidean Steiner tree problem
• Optimal binary space partitions in the plane
• Planar 3-SAT with a clause/variable cycle
• Planar 3DM is NP-complete
• Planar Formulae and Their Uses
• Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect
• Reducibility among combinatorial problems
• Selecting and covering colored points
• Sur le problème des courbes gauches en topologie.
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• The parameterized complexity of motion planning for snake-like robots
• The planar \(k\)-means problem is NP-hard
• The Rectilinear Steiner Arborescence Problem Is NP-Complete

This page was built for publication: Linear planar 3-SAT

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