木分解

グラフ理論において、木分解とはグラフから木へのマッピングであり、を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。 機械学習では、木分解はjunction tree、clique tree、join treeとも呼ばれ、確率伝搬法や制約充足問題、クエリ最適化、en:matrix decompositionのような問題で重要な役割を果たす。 木分解の概念は最初ににより導入された。後に andにより再発見され、以降他の多数の研究者たちに研究されている。