Output details
11 - Computer Science and Informatics
Royal Holloway, University of London
Article title
A unified theory of structural tractability for constraint satisfaction problems
Type
D - Journal article
Title of journal
Journal of Computer and System Sciences
Article number
-
Volume number
74
Issue number
5
First page of article
721
ISSN of journal
0022-0000
Year of publication
2008
Number of additional authors
2
Additional information
<11> This paper defines spread cuts, a new structural decomposition for databases and CSP, which puts all existing decompositions nicely into a clear unifying framework. This allows direct comparison between techniques - which had been contrived before. The proofs of the new decomposition and the examples are interesting in their own right. We have also improved the definition and proofs for the well-cited and useful hinge decomposition that we invented a few years earlier. This paper positions us at the forefront of research into structural decomposition techniques, which is a very active research area.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Centre for Algorithms and their Applications
Citation count
29
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
