The complexity of satisfiability problems
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- A refined branching algorithm for the maximum satisfiability problem
- As Close as It Gets
- Generating all maximal models of a Boolean expression
- MPF problem over modified medial semigroup is NP-complete
- Sandwiches for promise constraint satisfaction
- Strong Backdoors for Default Logic
- scientific article; zbMATH DE number 7204413 (Why is no real title available?)
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Generalized modal satisfiability
- Computational complexity studies of synchronous Boolean finite dynamical systems
- scientific article; zbMATH DE number 7378350 (Why is no real title available?)
- Locally consistent constraint satisfaction problems
- Coloring graphs without short cycles and long induced paths
- Polynomially solvable satisfiability problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Recent Results on the Algebraic Approach to the CSP
- Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
- scientific article; zbMATH DE number 1775445 (Why is no real title available?)
- Pushing vertices in digraphs without long induced cycles
- scientific article; zbMATH DE number 7536562 (Why is no real title available?)
- Satisfiability problems and algebras of Boolean constraint system games
- A perspective on certain polynomial-time solvable classes of satisfiability
- The Complexity of Very Simple Boolean Formulas with Applications
- Locally injective homomorphism to the simple weight graphs
- Implications of forbidden structures for extremal algorithmic problems
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- A survey on pairwise compatibility graphs
- Complexity of path-forming games
- Some variants of SAT and their properties
- On making directed graphs transitive
- On graphs that are not PCGs
- Colouring, constraint satisfaction, and complexity
- On the most imbalanced orientation of a graph
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- scientific article; zbMATH DE number 7561659 (Why is no real title available?)
- Particle swarm optimization for computing Nash and Stackelberg equilibria in energy markets
- Computational complexity of three-dimensional discrete tomography with missing data
- A simplified NP-complete satisfiability problem
- Hardness results on the man-exchange stable marriage problem with short preference lists
- Recognizing frozen variables in constraint satisfaction problems
- The complexity of minimizing wire lengths in VLSI layouts
- The expressive rate of constraints
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- The complexity of satisfiability problems: Refining Schaefer's theorem
- On the most imbalanced orientation of a graph
- Defensive alliances in signed networks
- On the Solvability Problem for Restricted Classes of Word Equations
- Decomposition into two trees with orientation constraints
- Finding \(d\)-cuts in graphs of bounded diameter, graphs of bounded radius and \(H\)-free graphs
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- SAT backdoors: depth beats size
- The complexity of weighted Boolean \#CSP with mixed signs
- Conjunctive query containment over trees
- The power of linear programming for general-valued CSPs
- Tractable structures for constraint satisfaction with truth tables
- On the complexity of deciding typability in the relational algebra
- Public-key cryptographic system based on generalized satisfiability problem
- The complexity of counting locally maximal satisfying assignments of Boolean CSPs
- Traveling salesman problems in temporal graphs
- The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I
- 2-colorable perfect matching is NP-complete in 2-connected 3-regular planar graphs
- Bases for Boolean co-clones
- Matchings, relaxed popularity, and optimality
- Data exchange: semantics and query answering
- The satisfiability constraint gap
- Algorithms and complexity of sandwich problems in graphs (extended abstract)
- A Complexity Index for Satisfiability Problems
- Time complexity of constraint satisfaction via universal algebra
- Reducibility among combinatorial problems
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Structural parameterizations for two bounded degree problems revisited
- On the (di)graphs with (directed) proper connection number two
- On the Complexity of Holant Problems
- Colouring H-free graphs of bounded diameter.
- Hybrid tractability of valued constraint problems
- On m-junctive predicates on a finite set
- Shortest reconfiguration paths in the solution space of Boolean formulas
- The \((n^ 2-1)\)-puzzle and related relocation problems
- Constraint satisfaction with counting quantifiers
- Dichotomy for finite tournaments of mixed-type
- The Complexity of theA B CProblem
- New results for the longest haplotype reconstruction problem
- Influence of tree topology restrictions on the complexity of haplotyping with missing data
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- Irregularity notions for digraphs
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Integer programming with 2-variable equations and 1-variable inequalities
- \(r\)-gathering problems on spiders: hardness, FPT algorithms, and PTASes
- A non-commuting stabilizer formalism
- Linear discrepancy is _2-hard to approximate
- Edge-disjoint branchings in temporal digraphs
- Sliding window temporal graph coloring
- Generalized satisfiability problems via operator assignments
- \(st\)-orientations with few transitive edges
- A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
- Generalized coloring of permutations
- The complexity of conservative valued CSPs
- Backdoors into heterogeneous classes of SAT and CSP
This page was built for publication: The complexity of satisfiability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402560)
