The Monotone Satisfiability Problem with Bounded Variable Appearances

DOI10.1142/S0129054118500168MaRDI QIDQ4963262zbMATH OpenOpenAlexFDO

Authors Andreas Darmann, Janosch Döcker, B. Dorn

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

(planar) monotone satisfiability3-satisfiabilitybounded variable appearancecomputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Precise upper and lower bounds for the monotone constraint satisfaction problem
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• Quantified constraint satisfaction on monoids
• On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy
• Complete problems for monotone NP
• Boundary properties of the satisfiability problems
• On bounded occurrence constraint satisfaction
• On the Monotone Upper Bound Problem
• On variable-weighted exact satisfiability problems
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics

Cites work

• A better heuristic for orthogonal graph drawings
• A simplified NP-complete satisfiability problem
• A special planar satisfiability problem and a consequence of its NP- completeness
• Complexity of automaton identification from given data
• Graph theory
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Optimal binary space partitions for segments in the plane
• Planar Formulae and Their Uses
• The Complexity of Multiterminal Cuts
• The Problem of Compatible Representatives
• Two-segmented channel routing is strong NP-complete

Cited in

(11)

• Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
• Orthogonal layout with optimal face complexity
• A social choice approach to ordinal group activity selection
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• Planar 3-SAT with a clause/variable cycle
• Mathematical Foundations of Computer Science 2003
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• Ultimate greedy approximation of independent sets in subcubic graphs
• Linear planar 3-SAT
• Complexity framework for forbidden subgraphs. I: The framework
• Computational complexity of some restricted instances of 3-SAT

This page was built for publication: The Monotone Satisfiability Problem with Bounded Variable Appearances

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