On the Parameterized Complexity of Exact Satisfiability Problems

No abstract is available for this paper.

• Publication year

  2005

• Venue

  International Symposium on Mathematical Foundations of Computer Science

• Publication date

  2005-08-29

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/11549345_49
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An algorithm for Exact Satisfiability analysed with the number of clauses as parameter

  2006influential reference
• A new algorithm for optimal 2-constraint satisfaction and its implications

  2005cited by this paper
• Exact 3-Satisfiability Is Decidable in Time O (2 0.16254 n )

  2005cited by this paper
• An efficient parameterized algorithm for m-set packing

  2004cited by this paper
• Maximum Exact Satisfiability: NP-completeness Proofs and Exact Algorithms

  2004influential reference
• Algorithms for four variants of the exact satisfiability problem

  2004cited by this paper
• Exact 3-satisfiability is decidable in time O(20.16254n)

  2004cited by this paper
• New algorithms for Exact Satisfiability

  2003influential reference
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT

  2003cited by this paper
• New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

  2000cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Parametrizing Above Guaranteed Values: MaxSat and MaxCut

  1997cited by this paper
• Satisfiability Is Quasilinear Complete in NQL

  1978cited by this paper
• Some Simplified NP-Complete Graph Problems

  1976cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper

• Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits

  2018cites this paper
• Improved exact algorithms for mildly sparse instances of Max SAT

  2017cites this paper
• Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction

  2014cites this paper
• Kernelization: New Upper and Lower Bound Techniques

  2009cites this paper
• Exact algorithms based on specific complexity measures for hard problems

  2007cites this paper
• A New Satisabilit y Algorithm With Applications To Max-Cut

  2005cites this paper