Fixed-Parameter Algorithms for Artificial Intelligence, Constraint Satisfaction, and Database ProblemsSurvey Paper, The Computer Journal, vol. 51, no. 3, pp. 303-325, 2008. Download: [download pdf] Abstract:We survey the parameterized complexity of problems that arise in artificial intelligence, database theory, and automated reasoning. In particular, we consider various parameterizations of the constraint satisfaction problem, the evaluation problem of Boolean conjunctive database queries, and the propositional satisfiability problem. Furthermore, we survey parameterized algorithms for problems arising in the context of the stable model semantics of logic programs, for a number of other problems of non-monotonic reasoning, and for the computation of cores in data exchange.[back to Stefan Szeider's homepage] |