New upper bounds for the problem of maximal satisfiability

DOI10.1515/DMA.2009.009zbMath1234.68154OpenAlexW2022837198MaRDI 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

zbMATH Keywords

upper boundsMAX-SATMAX-2-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (6)

New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ Unnamed Item

Uses Software

• SATO

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

This page was built for publication: New upper bounds for the problem of maximal satisfiability