@article{StructuralTractability,
  abstract = "In this paper we derive a generic form of structural decomposition for the constraint satisfaction problem, which we call a guarded decomposition. We show that many existing decomposition methods can be characterised in terms of finding guarded decompositions satisfying certain specified additional conditions. Using the guarded decomposition framework we are also able to define a new form of decomposition, which we call a spread-cut. We show that the discovery of width-k spread-cut decompositions is tractable for each k, and that spread-cut decompositions strongly generalise many existing decomposition methods. Finally we exhibit a family of hypergraphs Hn, for n=1,2,3..., where the minimum width of any hypertree decomposition of each Hn is 3n, but the width of the best spread-cut decomposition is only 2n+1.",
  author = "David Cohen and Peter Jeavons and Marc Gyssens",
  doi = "10.1016/j.jcss.2007.08.001",
  journal = "Journal of Computer and System Sciences",
  note = "Earlier, uncorrected, version appears in Proceedings of IJCAI'05, pp. 72--77: \url{http://www.ijcai.org/papers/0521.pdf}",
  pages = "721-743",
  title = "A unified theory of structural tractability for constraint satisfaction problems",
  url = "http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/JCSSspreadcut.pdf",
  volume = "74",
  year = "2008",
}