欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
研究了为无向连通子图设计环状遍历序列（TSC）的空间复杂性问题。通过定义对数空间的Cook归约，分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系，证明了TSC问题以及无向图遍历问题是对数空间可解的，并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。
英文摘要：
The space complexity of constructing cycle-like Traversal Sequences for（undirected） Connected Components （TSC） is studied.A new notion of log-space Cook reduction is put forward to analyze the relationships between TSC problem and the undirected connectivity and universal transversal sequence problems.It therefore implies that the TSC problem and traversal of undirected graph problem are equivalent and both solvable in log-space.The analyzing process produces a general approach of constructing TSC for any undirected graph.Finally,a specific but more efficient TSC construction algorithm for trees is also given.
同期刊论文项目
同项目期刊论文
期刊信息
位置：