Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems

被引：53

作者：

Gottlob, Georg ^{[2
]}

Szeider, Stefan ^{[1
]}

机构：

[1] Univ Durham, Sci Labs, Dept Comp Sci, Durham DH1 3LE, England

[2] Univ Oxford, Comp Lab, Oxford OX1 3QD, England

来源：

COMPUTER JOURNAL | 2008年 / 51卷 / 03期

基金：

英国工程与自然科学研究理事会;

关键词：

artificial intelligence; constraint satisfaction; parameterized algorithms;

D O I：

10.1093/comjnl/bxm056

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：303 / 325

页数：23

共 107 条

[41]

FERNAU H, 2005, THESIS U TUBINGEN

[42]

FISCHER E, IN PRESS LECT NOTES

[43] Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference [J].