補グラフ入力に対する線形時間グラフ探索アルゴリズム

被引用文献2件 参考文献4件

書誌事項

タイトル別名
  • Linear Time Graph Search Algorithms on Input of Complement Graphs

この論文をさがす

抄録

単純グラフは、補グラフを用いても表現できる。そこで枝数の少ない方を用いて表現する様にすれば、メモリー量を節約できる。この方式は問題の多項式可解性には影響を及ぼさないが、高速可解性、特に線形時間可解性に影響を及ぼす。すなわち、グラフで入力された問題例においては線形時間を保証するアルゴリズムも、補グラフで入力された問題例に対しては線形時間を保証するとは限らない。そこで本稿では補グラフ入力に対する、幅優先探索と深さ優先探索の線形時間アルゴリズムを与えた。これらを用いれば、他の問題に対する多くの線形時間アルゴリズムを、補グラフ入力上でも線形時間を保つ様にすることができる。

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (4)*注記

もっと見る

キーワード

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

  • CRID
    1571980077283183104
  • NII論文ID
    110003191490
  • NII書誌ID
    AN10013152
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ