低代价最短路径树快速算法的时间复杂度研究

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗.快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n e).FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的.通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!) e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n) e)更能体现FLSPT算法高效率.     

序贯LSB隐写术的提取攻击

序贯LSB隐写术在载体中通过连续LSB替换嵌入消息,其提取攻击问题本质上是消息嵌入起止点的估计问题。该文建立针对序贯LSB隐写术的提取攻击模型,将提取攻击问题转化为一类排序问题。对嵌入率未知情形,提出计算复杂度为O(n)的提取攻击算法。对嵌入率已知情形,给出计算复杂度为O(2logn)的快速提取攻击算法。实现了对序贯JSteg算法的提取攻击。     

一种改进的Voronoi图增量构造算法

Voronoi图是计算几何中的一种重要几何结构,也是计算几何的重要研究内容之一,如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用。增量法是最常用的构造Voronoi图的方法,但一般实现方法中点的定位时间比较长。扫描线算法可以视为一种特殊的增量法,时间复杂度为O(nlog n),但需要构造比较复杂的数据结构。为了更有效地构建Voronoi图,提出了一种改进的Voronoi图增量构造算法,该算法是通过对已有的生成Voronoi图的增量法进行分析,并结合它们的优点,采用扫描线的方式,通过右凸链的结构来定位新插入的点,实现了Voronoi图的逐步构造。和扫描线算法类似,其时间复杂度为O(nlog n),但算法更简洁,且便于理解和编程实现。     

一种同构、非同构布局模式构造算法

给出了一种基于完全关联图的准确构造同构、非同构布局模式的算法,并给出了其计算复杂度及适应范围.与李广强等（2003）的布局模式构造方法相比较表明,本算法能构造准确布局模式,适用范围较广,计算复杂度低,前者为O（n^3）,本文为O（n）,O（n^2）或O（n^3）.     

低度图的最大团求解算法

在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。     

一类双线性对的高效计算方案及在信息隐藏的应用

为了提高多媒体数据的基于身份加密的效率,构造计算安全的短签名与认证协议,建立一类双线性对的高效计算平台.构造一类具有确定嵌入次数的椭圆曲线,提出计算其有理点群阶的快速算法,时间复杂度比SEA,Satoh,SST 和 AGM等求阶算法更低.在此构造方案上,双线性对的计算无须借助复乘方法,总时间复杂度较低且实现容易,其结果可应用于信息隐藏领域.     

基于关联选择的可逆逻辑综合算法

可逆逻辑综合是可逆计算的重要内容,为了解决可逆逻辑综合中可逆电路构造和优化问题,提出一种基于关联选择的可逆逻辑综合算法及相应的优化算法.将可逆函数用真值表表示,按真值表从上往下的顺序综合,并若干相关联变量作为综合的目标位,分别计算相对混乱度和绝对混乱度,以最小混乱度原则选取可逆逻辑门.该算法及其优化算法的时间复杂度为O(n2×2n),空间复杂度为O(n×2n),优于最佳算法的空间复杂度O(2n!).通过C++语言实现对3变量全部函数及部分4变量函数的综合,并与其他可逆逻辑综合算法的结果及benchmark范例比较,结果表明平均门数均具有一定优势.     

多尺度特征融合的图嵌入方法

针对结构模式识别领域中通用图嵌入方法缺乏且计算复杂度较高的问题,基于空间句法理论提出一种融合多尺度特征的图嵌入方法。通过提取图的节点数、边数和智能度等全局特征、节点拓扑特征、边领域特征差异度和边拓扑特征差异度等局部特征和节点与边上的数值属性和符号属性等细节特征,利用多尺度直方图统计的方法构造描述图特征的特征向量,以此将桥梁将结构模式识别问题转化为统计模式识别问题,进而借助支持向量机(SVM)实现图的分类识别。实验结果表明,所提出的图嵌入方法在不同的图数据集上均具有较高的分类识别率。与其他图嵌入方法相比,该方法对图的拓扑表达能力强,并且可融合图的领域方面的非拓扑特征,通用性较好,计算复杂度较低。     

基于凸片段分解和格网的点在多边形中的可见边检测

检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算;然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化,其中n为多边形的边数.     

一类数据中心网络中顶点独立生成树的一种通用构造方法

数据中心网络设计的新趋势是在互连网络的顶点和边上分别部署交换机和双端口服务器,其逻辑图可以抽象为复合图.顶点独立生成树(node-independent spanning trees,NIST)是数据中心网络中的一种重要结构,可用于设计数据中心网络中的可靠通信协议,容错广播和安全消息分发,IP快速重路由等.给定一个复合图G(Kn),首先表明,如果图G的直径为d,则复合图G(Kn)的直径为2d或2d+1.假设n-正则、n-顶点连通的互连网络G中存在以任一顶点为根的n棵NIST,通过提出一种时间复杂度O(N)的高效算法(其中N是顶点数),给出了G(Kn)中一种构造n棵NIST的通用方法.对复合图Qn(Kn)的顶点分析表明,NIST的最大高度仅为其直径加3.另外,基于增广立方体的数据中心网络上的模拟实验也从另一个方面证明了上述结论的正确性.