Tree decomposition
id:
tree-decomposition-293-8207610
title:
Tree decomposition
text:
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 Rudolf Halin (1976).
brand slug:
wiki
category slug:
encyclopedia
description:
Mapping of a graph into a tree
original url:
https://en.wikipedia.org/wiki/Tree_decomposition
date created:
date modified:
2024-04-05T23:40:48Z
main entity:
{"identifier":"Q462095","url":"https://www.wikidata.org/entity/Q462095"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/a/a7/Tree_decomposition.svg","width":495,"height":657}
fields total:
13
integrity:
15