On the computational complexity of graph accessibility problem

6 References

Bibliographic Information

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

Search this article

Description

In this paper, we investigate the space complexity of the graph accessibility problem(alternatively called the st-connectivity problem). We first show that for a given(undirected or directed)graph G, the problem can be solved deterministically in space O(pw(G)^2log_2n), where n denotes the number of nodes and pw(G) denotes the path-width of G. As an immediate consequence, for the class of all graphs with path-width bounded above by a given constant, the problem can be solved deterministically in logarithmic space. As far as the authors know, there was no nontrivial class of graphs, except the class of cycle-free graphs, for which the problem is solvable in logarithmic space. Thus, our result observes a second nontrivial class of graphs with that property. We next show that for the class of all graphs consisting of only two paths, the problem still remains to be hard for deterministic log-space under the NC^1-reducibility. This result observes that the problem is essentially hard for deterministic log-space. We further exhibit some other problems to be hard for deterministic log-space.

Journal

References(6)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1574231877097564544
  • NII Article ID
    110003191668
  • NII Book ID
    AN10013152
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top