The minimum width of a tree decomposition. A tree has width at most one, while a clique of vertices forces width at least . Every pair of vertices in the clique shares a bag; their connected bag connected subgraphs of a tree have a common intersection by the Helly property of connected connected subgraphs of a tree, placing the whole clique in one bag. Small treewidth is useful for dynamic programming on finite-domain constraint satisfaction problems.
Articles by others on the same topic
Treewidth is a concept from graph theory that provides a measure of how "tree-like" a graph is. Specifically, the treewidth of a graph quantifies the minimum width of a tree decomposition of that graph. A tree decomposition is a way of representing a graph as a tree structure, where each node in the tree corresponds to a subset of vertices of the graph, satisfying certain properties.