正補混合表現によるグラフ探索時間の削減

スポンサーリンク

概要

論文の詳細を見る
単純グラフは補グラフを用いても表現でき、枝数が密である時は補グラフ表現の方がデータ量が少なくてすむ。ただこの表現法によって、これまで線形時間アルゴリズムであるとされてきたものに対して、線形時間可解性が保証されない可能性が生じる。しかし著者らによって、単純グラフに対する既存の線形時間探索アルゴリズムにおいて、補グラフ表現を用いても線形時間で動作するアルゴリズムが提案された。本報告では、グラフのそれぞれの節点の隣接枝数の密度に着目し、グラフ全体での枝数の密度に関係なく、グラフを表現するデータ量が削減できる単純グラフの表現法を提案する。そして、幅優先探索および深さ優先探索に対し、提案する表現法を用いても線形時間で動作するアルゴリズムを提案する。さらに、提案するアルゴリズムの計算時間を数値実験により評価し、その結果からグラフ探索時間の削減が可能であることが示された。
社団法人情報処理学会の論文
1998-07-22

著者

関連論文

もっと見る

スポンサーリンク