Perfect elimination とその効率的な導出
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)
「弦グラフ」の記事における「Perfect elimination とその効率的な導出」の解説
perfect elimination orderingとは、「隣接する頂点集合がクリークを形成しているグラフの頂点 v の削除」を繰り返し、グラフ全体が削除されるような順序付けである。グラフが弦グラフであれば、そしてその時に限りグラフはperfect elimination orderingを持つ。 Rose, Lueker & Tarjan (1976) (see also Habib et al. 2000) は、Lexicographic Breadth First Search と呼ばれる辞書順に並べながら探索する手法で、効率的に弦グラフのperfect elimination orderingが見つかると示した。このアルゴリズムは、グラフの頂点を集合列に以下の手法で分割する。まず、全ての頂点を含む1つの集合を考える。そして、一度も選ばれていない頂点を含む最初の集合 S から頂点 v を選び、S を「v に隣接している頂点」と「v に隣接していない頂点」の2つの集合に分割する。この分割を繰り返し、全ての頂点を一度ずつ選び終わったとき、perfect elimination orderingの逆の順に並ぶ。 lexicographic breadth first searchと、出力された順序がperfect elimination orderingかを確かめる処理は両方とも線形時間であるため、弦グラフに対して線形時間で処理可能である。弦グラフに対するprobe graph problemは多項式時間で解ける一方、弦グラフに対するGraph sandwich problemはNP完全である。 弦グラフに対する全てのperfect elimination ordering集合は反マトロイド(antimatroid)の基としてモデル化できる。例えば、Chandran et al. (2003)は与えられた弦グラフの全てのperfect elimination orderingsを効率的に列挙するアルゴリズムの一部として、反マトロイドへのこの接続を使いた。
※この「Perfect elimination とその効率的な導出」の解説は、「弦グラフ」の解説の一部です。
「Perfect elimination とその効率的な導出」を含む「弦グラフ」の記事については、「弦グラフ」の概要を参照ください。
- Perfect elimination とその効率的な導出のページへのリンク
