对数空间可构造的无向图遍历序列

• 作者: 石竑松 秦志光
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 对数空间复杂性 图的遍历 通用遍历序列 无向图连接性问题
• 年，卷（期）: 2010,（8）
• 所属期刊栏目: 博士论坛
• 页码范围: 11-15
• 页数: 5页
• 分类号: TP301
• 字数: 9363字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.08.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	秦志光	电子科技大学计算机科学与工程学院	262	3157	26.0	46.0
2	石竑松	电子科技大学计算机科学与工程学院	6	7	1.0	2.0