A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications (Q1759685): Difference between revisions

Latest revision as of 21:33, 5 July 2024

scientific article; zbMATH DE number 5823282

A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Application

Language	Label	Description	Also known as
English	A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications	scientific article; zbMATH DE number 5823282	A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Application

Statements

instance of

scholarly article

0 references

title

A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications (English)

0 references

A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Application (English)

0 references

0 references

0 references

Parameterized and Exact Computation

0 references

publication date

21 November 2012

0 references

7 December 2010

0 references

full work available at URL

https://arxiv.org/abs/1004.0526

0 references

zbMATH Keywords

MaxSAT

0 references

lower bound

0 references

2-satisfiable

0 references

fixed parameter tractable

0 references

kernel

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Kernels: Annotated, Proper and Induced

0 references

Lower Bounds for Kernelizations and Other Preprocessing Procedures

0 references

Implications of forbidden structures for extremal algorithmic problems

0 references

Partial Satisfaction of k-Satisfiable Formulas

0 references

Q5501275

0 references

Complexity of Partial Satisfaction

0 references

Complexity of partial satisfaction. II.

0 references

Parameterizing above Guaranteed Values: MaxSat and MaxCut

0 references

Q5710169

0 references

On Local Versus Global Satisfiability

0 references

On the Approximation of Maximum Satisfiability

0 references

Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas

0 references

Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.

0 references

A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application

0 references

Solving satisfiability in less than \(2^ n\) steps

0 references

Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

0 references

<i>E</i> <sub>11</sub> and M theory

0 references

Identifiers

zbMATH Open document ID

1252.68137

0 references

1309.68089

0 references

DOI

10.1007/s00453-011-9550-1

0 references

10.1007/978-3-642-17493-3_10

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1759685

@@ Property / cites work @@
+Kernels: Annotated, Proper and Induced
@@ Property / cites work: Kernels: Annotated, Proper and Induced / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Kernelizations and Other Preprocessing Procedures
+Normal rank
@@ Property / cites work @@
+Implications of forbidden structures for extremal algorithmic problems
+Normal rank
@@ Property / cites work @@
+Partial Satisfaction of k-Satisfiable Formulas
@@ Property / cites work: Partial Satisfaction of k-Satisfiable Formulas / rank @@
+Normal rank
@@ Property / cites work @@
+Q5501275
@@ Property / cites work: Q5501275 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Partial Satisfaction
@@ Property / cites work: Complexity of Partial Satisfaction / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of partial satisfaction. II.
@@ Property / cites work: Complexity of partial satisfaction. II. / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterizing above Guaranteed Values: MaxSat and MaxCut
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+On Local Versus Global Satisfiability
@@ Property / cites work: On Local Versus Global Satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+On the Approximation of Maximum Satisfiability
@@ Property / cites work: On the Approximation of Maximum Satisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
+Normal rank
@@ Property / cites work @@
+Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
+Normal rank
@@ Property / cites work @@
+A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
+Normal rank
@@ Property / cites work @@
+Solving satisfiability in less than \(2^ n\) steps
+Normal rank
@@ Property / cites work @@
+Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
+Normal rank
@@ Property / cites work @@
+<i>E</i>                     <sub>11</sub>                     and M theory
@@ Property / cites work: <i>E</i> <sub>11</sub> and M theory / rank @@
+Normal rank