论文研究-对数空间可构造的无向图遍历序列.pdf

研究了为无向连通子图设计环状遍历序列（TSC）的空间复杂性问题。通过定义对数空间的Cook归约，分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系，证明了TSC问题以及无向图遍历问题是对数空间可解的，并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。