Further improvements for SAT in terms of formula length

DOI10.1016/j.ic.2023.105085MaRDI QIDQ6077846

Mingyu Xiao, Junqiang Peng

Publication date: 27 September 2023

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

satisfiabilityworst-case analysisparameterized algorithmsmeasure-and-conqueramortized analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• Exact algorithms for dominating set
• Dealing with 4-variables by resolution: an improved MaxSAT algorithm
• Exact exponential algorithms.
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• An improved upper bound for SAT
• A satisfiability tester for non-clausal propositional calculus
• New worst-case upper bounds for SAT
• Exact algorithms for maximum independent set
• A fast algorithm for SAT in terms of formula length
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• An Improved SAT Algorithm in Terms of Formula Length
• A measure & conquer approach for the analysis of exact algorithms
• An improved exponential-time algorithm for k -SAT
• Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
• 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
• Algorithms – ESA 2005
• A Computing Procedure for Quantification Theory
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing
• Algorithms and Computation
• On the complexity of \(k\)-SAT

This page was built for publication: Further improvements for SAT in terms of formula length