交替哈密尔顿环存在性条件

本文讨论在研究“时间问题”(TTP)时遇到的有关理论,即在给定条件下可行时间表是否存在的判定问题:在作出了若干对应性的约束之后,TTP的存在性问题也就是交替哈密尔顿环的存在性问题.对AHC的存在性条件作了证明,并讨论了若干放松条件的可能性.

一个高效的3SAT到Hamilton环转化方法

为了得到将三元可满足性问题(3-Satisfiability problem,3SAT)直接转化为哈密尔顿环(Hamilton cycle)的高效转化方法,该文以长年对哈密尔顿环研究计算所探索出的规律为基础进行研究。通过对各种可能实现转化的图形组合进行全面的比较分析,得出用无向图的两个节点模拟3SAT的一个变量,用无向图的13个节点模拟3SAT的一个子式的方法,实现了3SAT到哈密尔顿环的高效转化。研究结果表明:该转化所需要的节点数及其边数是最优的。

构建网络的新方法:基于环路的混合交换光网络

为了能够更好地支持突发性数据业务,提出了一种新型网络交换结构——基于环路的混合交换光网络(cycle-based hybrid switching optical networks,CHSON)。该网络结合了光电路交换(OCS)和光突发交换(OBS)两种交换技术,不仅可以有效地降低网络节点的分组转发压力,而且能够较好地承载突发性数据业务。首先介绍了CHSON的网络结构和虚拓扑设计,然后阐述了节点设计及其执行流程。仿真表明,CHSON具有比OCS网络更低的丢包率,而且在丢包率和平均分组延时方面,CHSON较OBS网络有明显改善。