弦化(Chordal completion)と木幅
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)
「弦グラフ」の記事における「弦化(Chordal completion)と木幅」の解説
任意のグラフGの弦化とは、Gを部分グラフとして持つような弦グラフである。最小弦化は複数のパラメータに従う計算複雑性を持ち、準指数時間で解くことができる。Gの木幅はクリークのサイズが最小となるような弦化が施されたGの最大クリークの頂点数-1である。k-木は木幅をkより大きくしなければ辺を追加できないグラフである。したがって、k-木はそれ自身の弦化であり、弦グラフの一種である。弦化は他のグラフの特徴付にも使われる。
※この「弦化(Chordal completion)と木幅」の解説は、「弦グラフ」の解説の一部です。
「弦化(Chordal completion)と木幅」を含む「弦グラフ」の記事については、「弦グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「弦化と木幅」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 弦化と木幅のページへのリンク
