![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Tree_decomposition.svg/640px-Tree_decomposition.svg.png&w=640&q=50)
Tree decomposition
Mapping of a graph into a tree / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Tree decomposition?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
This article is about tree structure of graphs. For decomposition of graphs into trees, see Graph theory § Decomposition problems. For decomposition of trees in nature, see Nurse log.
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Tree_decomposition.svg/320px-Tree_decomposition.svg.png)
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,[1] and matrix decomposition.
The concept of tree decomposition was originally introduced by Rudolf Halin (1976). Later it was rediscovered by Neil Robertson and Paul Seymour (1984) and has since been studied by many other authors.[2]