区間completionとパス幅
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/06 10:20 UTC 版)
「区間グラフ」の記事における「区間completionとパス幅」の解説
任意のグラフ G に対する、 Gの区間completionとは、部分グラフとしてGを含む同じ頂点集合上の区間グラフである。パラメータ化された区間completion（k個の追加辺をもつ区間拡大グラフを見つける）は、準指数関数時間で解決可能である。 区間グラフのパス幅は最大クリークのサイズ-1であり、彩色数-1である。任意のグラフに対するパス幅はG を部分グラフとして含む区間グラフの最小のパス幅である。。
※この「区間completionとパス幅」の解説は、「区間グラフ」の解説の一部です。
「区間completionとパス幅」を含む「区間グラフ」の記事については、「区間グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「区間completionとパス幅」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 区間completionとパス幅のページへのリンク
