New upper bounds for the problem of maximal satisfiability
From MaRDI portal
Publication:3225865
DOI10.1515/DMA.2009.009zbMath1234.68154MaRDI QIDQ3225865
K. Kutskov, Alexander S. Kulikov
Publication date: 23 March 2012
Published in: Discrete Mathematics and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1515/dma.2009.009
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, A new upper bound for Max-2-SAT: A graph-theoretic approach, Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment, New exact algorithms for the 2-constraint satisfaction problem, Solving SCS for bounded length strings in fewer than \(2^n\) steps, New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
Uses Software
Cites Work
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- New methods for 3-SAT decision and worst-case analysis
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- A new algorithm for optimal 2-constraint satisfaction and its implications
- New Bounds for MAX-SAT by Clause Learning
- Algorithms for maximum independent sets
- MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time