On the Parameterized Complexity of Exact Satisfiability Problems.
Joachim KneisDaniel MölleStefan RichterPeter RossmanithPublished in: MFCS (2005)
Keyphrases
- satisfiability problem
- parameterized complexity
- np complete
- fixed parameter tractable
- search algorithm
- phase transition
- temporal logic
- sat problem
- bounded treewidth
- stochastic local search
- global constraints
- mazurkiewicz traces
- randomly generated
- sat instances
- computational complexity
- max sat
- symmetry breaking
- conjunctive queries
- computational problems
- model checking
- tabu search
- scheduling problem
- query language