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 Graph Search.
Concept
Treewidth
Summary
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.
Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other.
Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms. Many algorithms that are NP-hard for general graphs, become easier when the treewidth is bounded by a constant.
The concept of treewidth was originally introduced by under the name of dimension. It was later rediscovered by , based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by and has since been studied by many other authors.
A tree decomposition of a graph G = (V, E) is a tree T with nodes X_1, ..., X_n, where each X_i is a subset of V, satisfying the following properties (the term node is used to refer to a vertex of T to avoid confusion with vertices of G):
The union of all sets X_i equals V. That is, each graph vertex is contained in at least one tree node.
If X_i and X_j both contain a vertex v, then all nodes X_k of T in the (unique) path between X_i and X_j contain v as well. Equivalently, the tree nodes containing vertex v form a connected subtree of T.
For every edge (v, w) in the graph, there is a subset X_i that contains both v and w.
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.