New upper bounds for the problem of maximal satisfiability
From MaRDI portal
Publication:3225865
DOI10.1515/DMA.2009.009zbMATH Open1234.68154OpenAlexW2022837198MaRDI QIDQ3225865FDOQ3225865
Authors: 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
Recommendations
- New Upper Bounds for Maximum Satisfiability
- Publication:4938646
- scientific article; zbMATH DE number 1522934
- Upper bounds on the satisfiability threshold
- A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- New worst-case upper bound for counting exact satisfiability
Cites Work
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Algorithms for maximum independent sets
- New methods for 3-SAT decision and worst-case analysis
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- New Bounds for MAX-SAT by Clause Learning
- MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
Cited In (13)
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- Title not available (Why is that?)
- New exact algorithms for the 2-constraint satisfaction problem
- Achieving new upper bounds for the hypergraph duality problem through logic
- From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- Title not available (Why is that?)
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- A tighter upper bound for random MAX \(2\)-SAT
- New Bounds for MAX-SAT by Clause Learning
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- New Upper Bounds for Maximum Satisfiability
Uses Software
This page was built for publication: New upper bounds for the problem of maximal satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225865)
