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

参考文献4件

書誌事項

タイトル別名
  • Decrease in the time of graph search on original-complement-mixed representations

この論文をさがす

説明

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

収録刊行物

参考文献 (4)*注記

もっと見る

詳細情報 詳細情報について

  • CRID
    1570291227233474816
  • NII論文ID
    110002812145
  • NII書誌ID
    AN1009593X
  • ISSN
    09196072
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ