The Monotone Satisfiability Problem with Bounded Variable Appearances

DOI10.1142/S0129054118500168zbMath1398.68224OpenAlexW2894780622MaRDI QIDQ4963262

Britta Dorn, Andreas Darmann, Janosch Döcker

Publication date: 1 November 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054118500168

zbMATH Keywords

computational complexity3-satisfiability(planar) monotone satisfiabilitybounded variable appearance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Orthogonal layout with optimal face complexity ⋮ A social choice approach to ordinal group activity selection ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}

Cites Work

• Unnamed Item
• Unnamed Item
• A simplified NP-complete satisfiability problem
• A special planar satisfiability problem and a consequence of its NP- completeness
• Two-segmented channel routing is strong NP-complete
• A better heuristic for orthogonal graph drawings
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Complexity of automaton identification from given data
• The Complexity of Multiterminal Cuts
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE