到達可能性判定問題の計算量について

参考文献6件

書誌事項

タイトル別名
  • On the computational complexity of graph accessibility problem

この論文をさがす

説明

無向グラフならびに有向グラフの到着可能性判定問題(各々を, UGAPおよびGAPと略す)は, 1970年代から研究されている古い問題であるが, 領域量が限定された計算過程を具体的な計算問題という形に表現し直したものであり, 領域量に関わる計算量理論にとっては中心的な問題である.本稿ではまず, 無向グラフのパス幅をpw(G)で表すとき, UGAPが決定性O(pw(G)^2logn)領域で判定可能であることを示す.ここで, nは入力として与えられた無向グラフの頂点数を表す.また, これと同じ結果がGAPについても成立する.パス幅は最大でn-1になるので, この結果が極めて良好なものとは言えないが, それでも, パス幅が定数のグラフからなるクラスに対しては, UGAPやGAPが決定性対数領域で判定可能であることを示している.これまで, UGAPやGAPが決定性対数領域で判定可能となるようなクラスとしては無閉路的なグラフ(つまり, 森)のクラス以外には知られていなかった.従って, 本稿の結果はこれ以外の新たなクラスを初めて提示している.更に, 入力を二本の道からなるグラフに制限したとしても, UGAPが決定性対数領域困難(DLOG-hard)になることを示す.この結果は, 入力対象となる無向グラフの構造をどのように制限したとしても, (制限された)UGAPがDLOGより下位のクラス(例えば, NC^1やTC^0など)に属することはないことの強い根拠を与えている.

収録刊行物

参考文献 (6)*注記

もっと見る

キーワード

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

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

問題の指摘

ページトップへ