Space complexity of undirected graph accessibility problem

无向图可达性问题的空间复杂度

基本信息

批准号：
09640296
负责人：
TODA Seinosuke
金额：
$ 1.15万
依托单位：
Nihon University, College of Humanities and Sciences
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

项目摘要

In this research project, 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 solveddeterministically in space O(pw(G)^2 log_2 n), where n denotes the number of nodesand 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. We futher investigate the time compleixty of computing the number of isomorphisms between two given graphs. We obtain an algorithm for this problem wokring in time O(n^<k+4>) where n denotes the number of vertices in the graphs and k denotes the tree-width of the graphs.

在该研究项目中，我们研究了图形可访问性问题的空间复杂性（替代称为ST连接性问题）。 We first show that for a given (undirected or directed) graph G, the problem can be solveddeterministically in space O(pw(G)^2 log_2 n), where n denotes the number of nodesand 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 空间。据作者所知道的，除了无周期的图表外，没有非平凡的图形，在对数空间中可以解决该问题。因此，我们的结果观察了第二个与该属性的非平凡的图形类别。接下来，我们显示，对于仅由两条路径组成的所有图表的类别，对于NC^1可重新确定性下的确定性日志空间仍然很难。该结果观察到问题对于确定性日志空间本质上很难。我们进一步表现出一些其他问题，难以确定的日志空间。我们研究了计算两个给定图之间的同构数量的时间。我们在时间O（n^<k+4>）中获得了此问题的算法，其中n表示图中的顶点数，k表示图的树宽度。