Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Tree decomposition
Summary
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition.
The concept of tree decomposition was originally introduced by . Later it was rediscovered by and has since been studied by many other authors.
Intuitively, a tree decomposition represents the vertices of a given graph G as subtrees of a tree, in such a way that vertices in G are adjacent only when the corresponding subtrees intersect. Thus, G forms a subgraph of the intersection graph of the subtrees. The full intersection graph is a chordal graph.
Each subtree associates a graph vertex with a set of tree nodes. To define this formally, we represent each tree node as the set of vertices associated with it.
Thus, given a graph G = (V, E), a tree decomposition is a pair (X, T), where X = {X_1, ..., X_n} is a family of subsets (sometimes called bags) of V, and T is a tree whose nodes are the subsets X_i, satisfying the following properties:
The union of all sets X_i equals V. That is, each graph vertex is associated with at least one tree node.
For every edge (v, w) in the graph, there is a subset X_i that contains both v and w. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.
If X_i and X_j both contain a vertex v, then all nodes X_k of the tree in the (unique) path between X_i and X_j contain v as well. That is, the nodes associated with vertex v form a connected subset of T. This is also known as coherence, or the running intersection property. It can be stated equivalently that if X_i, X_j and X_k are nodes, and X_k is on the path from X_i to X_j, then .
The tree decomposition of a graph is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.