chapter 9

Tree Decomposition Methods

Everything should be made as simple as possible, but not one bit simpler.

Albert Einstein (attributed)

As noted in Chapters 4 and 8, topological characterization of tractable classes is centered on the graph parameter called induced width or tree width. In this chapter, we provide related schemes that are based on the notion of tree decompositions. These methods are applicable across a wide variety of tasks, not exclusively to constraint processing, and have received different names in different research areas, such as join-tree clustering, clique-tree clustering and hypertree decompositions. We will refer to these schemes by the umbrella term tree-clustering. The complexity of these methods is governed ...

Get Constraint Processing now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.