Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (8): 11-15.DOI: 10.3778/j.issn.1002-8331.2010.08.004

• 博士论坛 • Previous Articles     Next Articles

Log-space constructible traversal sequences for undirected graphs

SHI Hong-song,QIN Zhi-guang   

  1. School of Computer Science & Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China
  • Received:2009-11-23 Revised:2010-01-12 Online:2010-03-11 Published:2010-03-11
  • Contact: SHI Hong-song



  1. 电子科技大学 计算机科学与工程学院,成都 611731
  • 通讯作者: 石竑松

Abstract: 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.

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

CLC Number: