効率的なアルゴリズム

ウィキペディア小見出し辞書

効率的なアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/06 10:20 UTC 版)

「区間グラフ」の記事における「効率的なアルゴリズム」の解説

与えられたグラフ G = (V, E) が区間グラフであるかは、頂点被覆に関して連続な G の極大クリークの順番を求めることで O(|V|+|E|) 時間で判別できる。[要出典] Booth & Lueker (1976)による線形時間アルゴリズムはPQ-木を用いたデータ構造をベースにしていた複雑な手法であったが、Habib et al. (2000)が「区間グラフは弦グラフかつ補グラフが比較可能グラフである」という性質を用い、よりシンプルな辞書順幅優先探索を用いた手法を示した。Corneil, Olariu & Stewart (2009)に6-sweep 辞書順幅優先探索を用いた手法も紹介されている。

効率的なアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:51 UTC 版)

「置換グラフ」の記事における「効率的なアルゴリズム」の解説

与えられたグラフが置換グラフであるかを判定し、もし置換グラフであればその置換を導出する処理は、線形時間で処理可能である。 一般のグラフに対してはNP-完全であるような問題に対しても、入力が置換グラフであれば、パーフェクトグラフの一種として、効率的なアルゴリズムが存在する場合がある。 置換グラフの最大クリークはグラフを定義する順列の最長増加（減少）部分列に対応するため、最長増加（減少）部分列を導出するアルゴリズムを使用して、置換グラフの最大クリーク問題を多項式時間で解くことが可能。 同様に、置換において増加部分列は、対応する置換グラフにおける同じサイズの独立集合に対応する。 置換グラフの木幅 と パス幅 は多項式時間で計算できる。そのアルゴリズムは、頂点分離の数がグラフのサイズの多項式で表されることに由来する。