@inproceedings{Cooper2008:hybrid,
  abstract = "The constraint satisfaction problem (CSP) is a central generic problem in artificial intelligence. Considerable progress has been made in identifying properties which ensure tractability in such problems, such as the property of being tree-structured. In this paper we introduce the broken-triangle property, which allows us to define a hybrid tractable class for this problem which significantly generalizes the class of problems with tree structure. We show that the broken-triangle property is conservative (i.e., it is preserved under domain reduction and hence under arc consistency operations) and that there is a polynomial-time algorithm to determine an ordering of the variables for which the broken-triangle property holds (or to determine that no such ordering exists). We also present a non-conservative extension of the broken-triangle property which is also sufficient to ensure tractability and can be detected in polynomial time.",
  author = "Martin C. Cooper and Peter G. Jeavons and Andr{\'a}s Z. Salamon",
  booktitle = "{ECAI} 2008, Proceedings of the 18th European Conference on Artificial Intelligence, July 21--25, Patras, Greece",
  editor = "Malik Ghallab, Constantine D. Spyropoulos, Nikos Fakotakis, Nikos Avouris",
  isbn = "978-1-58603-891-5",
  issn = "0922-6389",
  note = "Best paper award.",
  pages = "530--534",
  publisher = "IOS Press",
  series = "Frontiers in Artificial Intelligence and Applications",
  title = "Hybrid tractable {CSP}s which generalize tree structure",
  url = "http://www.gaon.net/andras/academic/cjs-ecai2008.pdf",
  volume = "178",
  year = "2008",
}