木幅
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 01:24 UTC 版)
詳細は「en:Treewidth」を参照 木分解の幅はその最大の集合Xiの大きさ引く1である。グラフGの木幅 tw(G)はすべての可能なGの木分解の幅の最小値である。この定義では、木の木幅を1とするために最大の集合の大きさから1を引いている。木幅は木分解以外の構造からも定義することができる。たとえば弦グラフやbrambles、havensなどである。 与えられたグラフGの木幅が与えられた上限k以下であるかどうかを決定する問題はNP完全である。しかし、kが固定された定数である場合、木幅kのグラフの認識と、幅kの木分解の構成は線型時間で可能である。時間計算量はkについては指数関数的に増加する。
※この「木幅」の解説は、「木分解」の解説の一部です。
「木幅」を含む「木分解」の記事については、「木分解」の概要を参照ください。
ウィキペディア小見出し辞書の「木・幅」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 木・幅のページへのリンク
