A tree of bags of graph vertices such that every vertex occurs in a bag, both endpoints of every graph edge occur together in a bag, and the bags containing any fixed vertex form a connected connected subgraph of a tree. Its width is . The connected-occurrence condition lets subproblems agree on shared variables while solving a constraint satisfaction problem; an arbitrary cover of edges by small bags is insufficient.
New to topics? Read the docs here!