Algorithms for four variants of the exact satisfiability problem

DOI10.1016/J.TCS.2004.02.035zbMATH Open1068.68068OpenAlexW2089328544MaRDI QIDQ596105FDOQ596105

Richard Beigel, Peter Jonsson, Vilhelm Dahllöf

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.035

zbMATH Keywords

ExactAlgorithmSAT3-satisfiabilityExact solutionComputational complexity3-SatisfiabilityCountingCounting modelsCounting problemExact satisfiabilityExponential-time algorithmSatisfiabilityX3SATXSAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• Algorithms for Sat and upper bounds on their complexity
• On the hardness of approximate reasoning
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• A Computing Procedure for Quantification Theory
• The complexity of counting in sparse, regular, and planar graphs
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• Algorithms for maximum independent sets
• New methods for 3-SAT decision and worst-case analysis
• An improved exponential-time algorithm for k -SAT
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Theory and Applications of Satisfiability Testing
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• The Complexity of Planar Counting Problems
• Counting the number of solutions for instances of satisfiability
• Faster exact solutions for some NP-hard problems.
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Number of models and satisfiability of sets of clauses

Cited In (11)

• Metalevel algorithms for variant satisfiability
• Exact algorithms for exact satisfiability and number of perfect matchings
• Sort and Search: exact algorithms for generalized domination
• Exactly hittable interval graphs
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY
• Partition into triangles on bounded degree graphs
• Local search strikes again: PTAS for variants of geometric covering and packing
• New algorithms for exact satisfiability
• Improved algorithms for the general exact satisfiability problem
• On variable-weighted exact satisfiability problems

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Algorithms for the maximum satisfiability problem 👍 👎
• Exact algorithms for exact satisfiability and number of perfect matchings 👍 👎
• New algorithms for exact satisfiability 👍 👎
• Improved algorithms for the general exact satisfiability problem 👍 👎
• An improved exact algorithm for the exact satisfiability problem 👍 👎
• An exact and a randomized approach for the satisfiability problem 👍 👎
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings 👍 👎
• Theory and Applications of Satisfiability Testing 👍 👎

This page was built for publication: Algorithms for four variants of the exact satisfiability problem

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