On variable-weighted exact satisfiability problems

DOI10.1007/S10472-007-9084-ZzbMATH Open1127.68100OpenAlexW1996763543MaRDI QIDQ2462633FDOQ2462633

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

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

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)

Cites Work

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

Cited In (14)

• Faster 3-coloring of small-diameter graphs
• New worst-case upper bound for counting exact satisfiability
• Algorithms for Variable-Weighted 2-SAT and Dual Problems
• Metalevel algorithms for variant satisfiability
• 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)