clique tree | join tree | junction tree

A tree decomposition is a mapping of a graph into a related tree with desirable properties that allow it to be used to efficiently compute certain properties (e.g., independence polynomial) of the original graph. The tree decomposition of a graph is not unique and need not be isomorphic to the original graph. Tree decompositions are also known as clique trees, join trees, and junction trees. A measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition is known as the treewidth.

tree | treewidth