Publication:4747916
From MaRDI portal
zbMath0508.90065MaRDI QIDQ4747916
Burkhard Monien, Ewald Speckenmeyer, O. Vornberger
Publication date: 1981
computational complexity; upper bounds; NP-completeness; worst case analysis; covering problems; exact satisfiability; exact set cover
Related Items
Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, An improved upper bound for SAT, Exact algorithms for exact satisfiability and number of perfect matchings, An algorithm for exact satisfiability analysed with the number of clauses as parameter, Exact satisfiability, a natural extension of set partition, and its average case behavior, New algorithms for exact satisfiability, Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\), Partition into triangles on bounded degree graphs, XSAT and NAE-SAT of linear CNF classes, On variable-weighted exact satisfiability problems, An upper bound \(O(2^{0.16254n})\) for exact 3-satisfiability: a simpler proof, Improved worst-case complexity for the MIN 3-SET COVERING problem, On Some SAT-Variants over Linear Formulas