Improved exact algorithms for MAX-SAT
From MaRDI portal
Publication:1878397
DOI10.1016/J.DAM.2003.03.002zbMATH Open1077.68116OpenAlexW2148185803MaRDI QIDQ1878397FDOQ1878397
Authors: Jianer Chen, Iyad Kanj 
Publication date: 19 August 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2003.03.002
Recommendations
Cites Work
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Title not available (Why is that?)
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- A Computing Procedure for Quantification Theory
- An improved fixed-parameter algorithm for vertex cover
- Title not available (Why is that?)
- Algorithms for maximum independent sets
- Vertex cover: Further observations and further improvements
- Title not available (Why is that?)
- Algorithms for the maximum satisfiability problem
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- A general method to speed up fixed-parameter-tractable algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- New Upper Bounds for Maximum Satisfiability
- Title not available (Why is that?)
- Title not available (Why is that?)
- An efficient exact algorithm for constraint bipartite vertex cover
- Title not available (Why is that?)
- Title not available (Why is that?)
- On fixed-parameter tractability and approximability of NP optimization problems
- Integrity constraints in logic databases
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (29)
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- A Complete Calculus for Max-SAT
- Algorithms and Computation
- Title not available (Why is that?)
- A refined branching algorithm for the maximum satisfiability problem
- Dealing with 4-variables by resolution: an improved \textsc{MaxSAT} algorithm
- Solving MAX-\(r\)-SAT above a tight lower bound
- New exact algorithms for the 2-constraint satisfaction problem
- A new algorithm for parameterized MAX-SAT
- Almost 2-SAT is fixed-parameter tractable
- Improved parameterized set splitting algorithms: A Probabilistic approach
- On the parallel parameterized complexity of MaxSAT variants
- Title not available (Why is that?)
- Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
- Improvements to Hybrid Incremental SAT Algorithms
- Exact algorithms for MAX-SAT
- Title not available (Why is that?)
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
- Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
- Improved \textsc{MaxSAT} algorithms for instances of degree 3
- Theory and Applications of Satisfiability Testing
- Moderately exponential time and fixed parameter approximation algorithms
- Dealing with 4-variables by resolution: an improved MaxSAT algorithm
- Using the method of conditional expectations to supply an improved starting point for CCLS
- Improved exact algorithms for mildly sparse instances of MAX SAT
Uses Software
This page was built for publication: Improved exact algorithms for MAX-SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1878397)
