| 对数空间可构造的无向图遍历序列 |
| |
| 引用本文： | 石竑松,秦志光.对数空间可构造的无向图遍历序列[J].计算机工程与应用,2010,46(8):11-15. |
| |
| 作者姓名： | 石竑松 秦志光 |
| |
| 作者单位： | 电子科技大学,计算机科学与工程学院,成都,611731 |
| |
| 基金项目： | 国家高技术研究发展计划(863)Grant No.2006AA01Z428;;国家自然科学基金Grant No.60673075~~ |
| |
| 摘 要： | 研究了为无向连通子图设计环状遍历序列（TSC）的空间复杂性问题。通过定义对数空间的Cook归约，分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系，证明了TSC问题以及无向图遍历问题是对数空间可解的，并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。
|
| 关 键 词： | 对数空间复杂性 图的遍历 通用遍历序列 无向图连接性问题 |
| 收稿时间： | 2009-11-23 |
| 修稿时间： | 2010-1-12
|
Log-space constructible traversal sequences for undirected graphs |
| |
| SHI Hong-song,QIN Zhi-guang.Log-space constructible traversal sequences for undirected graphs[J].Computer Engineering and Applications,2010,46(8):11-15. |
| |
| Authors: | SHI Hong-song QIN Zhi-guang |
| |
| Affiliation: | SHI Hong-song,QIN Zhi-guang School of Computer Science & Engineering,University of Electronic Science , Technology of China,Chengdu 611731,China |
| |
| 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 u... |
| |
| Keywords: | log-space complexity graph traversal universal travemal sequences Undirected Connectivity(UCONN) |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
