Algorithms for four variants of the exact satisfiability problem
From MaRDI portal
Publication:596105
DOI10.1016/j.tcs.2004.02.035zbMath1068.68068MaRDI QIDQ596105
Peter Jonsson, Richard Beigel, Vilhelm Dahllöf
Publication date: 10 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.035
Exact; Algorithm; Satisfiability; Computational complexity; Exact solution; SAT; 3-satisfiability; 3-Satisfiability; Counting; Counting models; Counting problem; Exact satisfiability; Exponential-time algorithm; X3SAT; XSAT
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Exact algorithms for exact satisfiability and number of perfect matchings, New algorithms for exact satisfiability, On variable-weighted exact satisfiability problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Number of models and satisfiability of sets of clauses
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- Faster exact solutions for some NP-hard problems.
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- New methods for 3-SAT decision and worst-case analysis
- Counting the number of solutions for instances of satisfiability
- Algorithms for Sat and upper bounds on their complexity
- On the hardness of approximate reasoning
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- An improved exponential-time algorithm for k -SAT
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- Algorithms for maximum independent sets
- The Complexity of Enumeration and Reliability Problems
- The Complexity of Planar Counting Problems
- Counting Unlabelled Subtrees of a Tree is #P-complete
- Theory and Applications of Satisfiability Testing
- A Computing Procedure for Quantification Theory
