Improved algorithms for the general exact satisfiability problem

DOI10.1016/j.tcs.2021.07.036OpenAlexW3190027049MaRDI QIDQ2232607

Gordon Hoi, Frank Stephan

Publication date: 6 October 2021

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

Full work available at URL: https://arxiv.org/abs/2101.08637

zbMATH Keywords

exponential time algorithmsmeasure and conquerDPLL

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Algorithms for four variants of the exact satisfiability problem
• Exact exponential algorithms.
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• Exact algorithms for exact satisfiability and number of perfect matchings
• New algorithms for exact satisfiability
• New methods for 3-SAT decision and worst-case analysis
• An improved exact algorithm for the exact satisfiability problem
• A measure & conquer approach for the analysis of exact algorithms
• Solving SAT and SAT Modulo Theories
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• The complexity of satisfiability problems
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• The complexity of theorem-proving procedures
• Logic for Programming, Artificial Intelligence, and Reasoning
• Algorithms and Computation

This page was built for publication: Improved algorithms for the general exact satisfiability problem