大规模不确定图上的Top-k极大团挖掘算法

该文研究了从不确定图中挖掘出前k个出现概率最高的极大团的问题,提出了一种基于划分的高效并行算法.在该算法中,输入的大规模不确定图首先被划分为若干互不重叠的规模较小的子图,每个子图通过扩展邻居结点信息成为扩展子图.而后,应用改进后的分支界限搜索策略,并行挖掘各个扩展子图,以得到局部top-k结果.最后,归并所有的局部top-k结果,得到全局top-k极大团.同时,该文还提出了两种预处理策略,以提高算法效率.并且严格证明了算法的正确性.在多组不确定图数据集上的实验结果表明,算法具有很高的效率和很好的实用性.

基于OBDD的含圈与或图搜索算法研究

在含圈与或图理论框架基础上,给出了基于OBDD的含圈与或图符号表示方法,并提出了一种求解含圈与或图最小代价解图的符号搜索算法。实验结果表明,该算法在处理大规模含圈与或图时具有明显优势。

一种基于DT-MSN的性能预评估方法

为提高网络的利用率,解决DT-MSN中网络部署问题,运用子图的扩展理论,给出一种判定是否存在和全网同构的样本网络方法。在存在样本网络的前提下,用最小生成树原理提出一种基于节点间最大连接次数的节点分簇算法。该算法可以构建一种样本网络,在投递的数据流上和全网同构。构建一个样本网络场景,并和全网作实验对比分析。结果表明,构建样本网络模型可以代替全网做性能的预评估,能为部署大型网络场景提供可靠的性能评估报告,具有较好的实际应用价值。

集成电路模板提取算法综述

数据通路型集成电路中存在着高度的规律性，利用其规律性可以实现规则的布图以提高芯片的性能。该文介绍了基于图论的集成电路模板提取算法的研究进展情况，给出了TREE、SPOG和FAN等典型模板提取算法的思想，综合分析了各算法的优缺点及其适用情况，总结并比较了模板提取算法的一些重要性质，并对未来模板提取技术作了一下展望。