In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph. The treewidth measures the number of graph vertices mapped onto any tree node in an optimal tree decomposition. While it is NP-hard to determine the treewidth of a graph, many NP-hard combinatorial problems on graphs are solvable in polynomial time when restricted to graphs of bounded treewidth.
In machine learning, 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 decompositions and treewidth was originally introduced by Halin (1976). Later it was rediscovered by Robertson & Seymour (1984) and has since been studied by many other authors.
Read more about Tree Decomposition: Definition, Treewidth, Graph Minors, Dynamic Programming, Treewidth of Cliques, Treewidth of Trees
Famous quotes containing the word tree:
“Books, gentlemen, are a species of men, and introduced to them you circulate in the “very best society” that this world can furnish, without the intolerable infliction of “dressing” to go into it. In your shabbiest coat and cosiest slippers you may socially chat even with the fastidious Earl of Chesterfield, and lounging under a tree enjoy the divinest intimacy with my late lord of Verulam.”
—Herman Melville (1819–1891)