Skip Navigation



The Computer Journal Advance Access published online on September 5, 2007
The Computer Journal, doi:10.1093/comjnl/bxm056
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
51/3/303    most recent
bxm056v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Gottlob, G.
Right arrow Articles by Szeider, S.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2007. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Fixed-Parameter Algorithms For Artificial Intelligence, Constraint Satisfaction and Database Problems

Georg Gottlob1 and Stefan Szeider2,*

1 Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
2 Department of Computer Science, Science Labs, Durham University, South Road, DH1 3LE Durham, UK

* Corresponding author: stefan.szeider{at}durham.ac.uk

Received 15 March 2006; revised 25 October 2006

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.

Key Words: artificial intelligence • constraint satisfaction • parameterized algorithms


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.