scientific article; zbMATH DE number 3803174

zbMath0508.90065MaRDI QIDQ4747916

Burkhard Monien, Ewald Speckenmeyer, O. Vornberger

Publication date: 1981

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

computational complexityupper boundsNP-completenessworst case analysiscovering problemsexact satisfiabilityexact set cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Related Items (15)

An improved upper bound for SAT ⋮ Exact satisfiability, a natural extension of set partition, and its average case behavior ⋮ Improved worst-case complexity for the MIN 3-SET COVERING problem ⋮ Partition into triangles on bounded degree graphs ⋮ Further improvements for SAT in terms of formula length ⋮ XSAT and NAE-SAT of linear CNF classes ⋮ On variable-weighted exact satisfiability problems ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ New algorithms for exact satisfiability ⋮ Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\) ⋮ On Some SAT-Variants over Linear Formulas ⋮ An algorithm for exact satisfiability analysed with the number of clauses as parameter ⋮ Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems ⋮ An upper bound \(O(2^{0.16254n})\) for exact 3-satisfiability: a simpler proof ⋮ A fast algorithm for SAT in terms of formula length

This page was built for publication: