计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2010年
8期
11-15
,共5页
对数空间复杂性%图的遍历%通用遍历序列%无向图连接性问题
對數空間複雜性%圖的遍歷%通用遍歷序列%無嚮圖連接性問題
대수공간복잡성%도적편력%통용편력서렬%무향도련접성문제
log-space complexity%graph traversal%universal travemal sequences%Undirected Connectivity(UCONN)
研究了为无向连通子图设计环状遍历序列(TSC)的空间复杂性问题.通过定义对数空间的Cook归约,分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系,证明了TSC问题以及无向图遍历问题是对数空间可解的,并给出了一个TSC一般性构造方法.最后还提出了一个更有效的针对树状图的TSC构造算法.
研究瞭為無嚮連通子圖設計環狀遍歷序列(TSC)的空間複雜性問題.通過定義對數空間的Cook歸約,分析瞭TSC問題與無嚮圖連接性問題及通用遍歷序列構造問題的關繫,證明瞭TSC問題以及無嚮圖遍歷問題是對數空間可解的,併給齣瞭一箇TSC一般性構造方法.最後還提齣瞭一箇更有效的針對樹狀圖的TSC構造算法.
연구료위무향련통자도설계배상편력서렬(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.
