On variable-weighted exact satisfiability problems

DOI10.1007/S10472-007-9084-ZMaRDI QIDQ2462633zbMATH OpenOpenAlexFDO

Authors Stefan Porschen

Publication date 3 December 2007

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL http://e-archive.informatik.uni-koeln.de/526/2/zaik2006-526.pdf

zbMATH Keywords

NP-completenessCombinatorial optimizationCounting problemPerfect matchingExact algorithmSet partitionMaximum weight independent setWeighted exact satisfiability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Recommendations

• Algorithms and Computation
• SOFSEM 2005: Theory and Practice of Computer Science
• Counting All Solutions of Minimum Weight Exact Satisfiability
• Algorithms for Variable-Weighted 2-SAT and Dual Problems
• New worst-case upper bound for counting exact satisfiability

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 515943 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3803174 (Why is no real title available?)
• scientific article; zbMATH DE number 2119675 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Algorithms and Computation
• Algorithms for four variants of the exact satisfiability problem
• Counting All Solutions of Minimum Weight Exact Satisfiability
• Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)
• New algorithms for exact satisfiability
• SOFSEM 2005: Theory and Practice of Computer Science
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing

Cited in

(14)

• Faster 3-coloring of small-diameter graphs
• New worst-case upper bound for counting exact satisfiability
• Metalevel algorithms for variant satisfiability
• Algorithms for Variable-Weighted 2-SAT and Dual Problems
• Improved fixed-parameter algorithm for the minimum weight 3-SAT problem
• Algorithms and Computation
• Counting All Solutions of Minimum Weight Exact Satisfiability
• Solving satisfiability problems using elliptic approximations. A note on volumes and weights
• Estimating satisfiability
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Variant-Based Satisfiability in Initial Algebras
• Polynomial calculus for optimization
• Weighted NP Optimization Problems: Logical Definability and Approximation Properties
• SOFSEM 2005: Theory and Practice of Computer Science

This page was built for publication: On variable-weighted exact satisfiability problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2462633)