New Upper Bounds for Maximum Satisfiability
From MaRDI portal
Publication:4500858
DOI10.1006/JAGM.2000.1075zbMATH Open0959.68049OpenAlexW2154474334MaRDI QIDQ4500858FDOQ4500858
Authors: Rolf Niedermeier, Peter Rossmanith 
Publication date: 6 May 2001
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/385c20806ee166f3ba62205793c13b6e28f5b3f2
Recommendations
- New upper bounds for the problem of maximal satisfiability
- Publication:4938646
- scientific article; zbMATH DE number 1522934
- Upper bounds on the satisfiability threshold
- New worst-case upper bounds for SAT
- New worst-case upper bounds for SAT
- A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
- A new upper bound for Max-2-SAT: A graph-theoretic approach
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (52)
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- A Complete Calculus for Max-SAT
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- New upper bounds for the problem of maximal satisfiability
- New worst-case upper bounds for SAT
- New worst-case upper bounds for SAT
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- An efficient fixed-parameter algorithm for 3-hitting set
- Title not available (Why is that?)
- A refined branching algorithm for the maximum satisfiability problem
- Parameterizing above or below guaranteed values
- Worst-case study of local search for MAX-\(k\)-SAT.
- Breaking Cycle Structure to Improve Lower Bound for Max-SAT
- Resolution for Max-SAT
- A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
- Local maxima and improved exact algorithm for MAX-2-SAT
- Improving exact algorithms for MAX-2-SAT
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- Title not available (Why is that?)
- A Max-SAT Inference-Based Pre-processing for Max-Clique
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Title not available (Why is that?)
- A logical approach to efficient Max-SAT solving
- Exact algorithms for MAX-SAT
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- Exact Max 2-Sat: Easier and Faster
- Understanding the power of Max-SAT resolution through up-resilience
- A note on the complexity of minimum dominating set
- Iterative and core-guided maxsat solving: a survey and assessment
- 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
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Boosting branch-and-bound MaxSAT solvers with clause learning
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An Empirical Study of MAX-2-SAT Phase Transitions
- An efficient solver for weighted Max-SAT
- A new upper bound for \(( n , 3)\)-MAX-SAT
- Incomplete inference for graph problems
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- A tighter upper bound for random MAX \(2\)-SAT
- New Bounds for MAX-SAT by Clause Learning
- New tableau characterizations for non-clausal \textsc{MaxSAT} problem
- A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
- \textsc{ahmaxsat}: description and evaluation of a branch and bound Max-SAT solver
- Computational protein design as an optimization problem
- Improved exact algorithms for MAX-SAT
- Dealing with 4-variables by resolution: an improved MaxSAT algorithm
- An improved upper bound for SAT
- 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: New Upper Bounds for Maximum Satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500858)
