A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.     

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs

We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems. Received January 1995; revised February 1997.     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

一种基于图同构和单向置换的报文摘要构造算法

为了保护信息的机密性和完整性,该文给出了一种新的报文摘要构造算法,这种新算法是基于图同构的。为了把报文与图联系起来,采用了基于单向置换的报文摘要生成算法,并证明了对该算法而言,不存在多项式时间的概率算法来找到一个“冲突”。最后给出了类似于MD5算法的构造实例。     

A Heuristic Algorithm of Recognition of Isomorphism of Graphs

A heuristic polynomial algorithm is presented, which is used for the recognition of isomorphism of graphs and can be assigned to the group of methods that use local characteristic invariants of graphs. At each step, the behavior of the algorithm depends on information obtained at its previous steps. All the theorems stated are proved for a class of nonoriented graphs.     

最小二乘分解算法在车型识别中的应用

提出一种最小二乘支持向量机的序贯最小分类分解算法.针对最小二乘支持向量机,通过对核函数的相关变换,将二阶的误差信息归结到优化方程的一阶信息中,从而简化运算过程.采用最优函数梯度二阶信息选择工作集,实现最小二乘支持向量机分解算法,提高了算法的收敛性.采用径向基核函数和交叉验证网格搜索的方法验证算法的分类准确性.实验结果表明,提出的分类算法应用于车型识别中,可以得到比其他分类方法更好的分类准确度.     

Shift Register Graphs and Permutation/Reset Automata

Abstract

This note completes the author's study of embedding of cascade products of permutation or reset automata in so-called shift register graphs.     

最佳并行排列组合算法

本文给出两个新的最佳并行排列组合算法。这里所说的排列组合均指从n个元素中取m个元素的排列和组合处理。算法可运行于一种非常简单的并行计算模型上,它由k个同步运行的处理机构成,其中1≤k≤N,N为要处理的元素个数。当1≤k≤N/n,算法需O(「N/k」·h)时间。     

An Incremental Distributed Algorithm for Computing Biconnected Components in Dynamic Graphs

This paper describes a distributed algorithm for computing the biconnected components of a dynamically changing graph. Our algorithm has a worst-case communication complexity of O(b+c) messages for an edge insertion and O(b'+c) messages for an edge removal, and a worst-case time complexity of O(c) for both operations, where c is the maximum number of biconnected components in any of the connected components during the operation, b is the number of nodes in the biconnected component containing the new edge, and b' is the number of nodes in the biconnected component just before the deletion. The algorithm is presented in two stages. First, a serial algorithm is presented in which topology updates occur one at a time. Then, building on the serial algorithm, an algorithm is presented in which concurrent update requests are serialized within each connected component. The problem is motivated by the need to implement causal ordering of messages efficiently in a dynamically changing communication structure. Received January 1995; revised February 1997.     

一种用于动态图像序列的人脸识别算法

研究基于动态图像序列的人脸准确识别。人体在运动的过程中,脸部会发生较大幅度的震动,造成人脸姿态特征不可避免的发现形变,造成对图像的干扰,识别误差较大。传统的识别方法多是以人脸姿态特征作为识别的基础的静态识别,一旦人体运动幅度加大,人脸姿态特征发生变化,必然造成识别的准确度下降。为了避免上述问题,提出了一种利用Curvelet布尔核转换的动态图像序列人脸识别的算法。利用Curvelet转换算法对全部动态图像序列相关参数进行降维处理,利用布尔核转换将形变较大的人脸关键细节特点进行约束分类,建立多约束的完整动态人脸特征模型,保证姿态形变可控,最终实现了运动中的人脸识别。实验证明,利用上述算法进行运动中的人脸识别,提高了人脸识别的准确率。     

基于无线传感器网络的动态手势识别算法及动态演示

与语言文字一样,手势是人类沟通交流的重要方式。在计算机技术高速发展的现在,手势识别技术的出现,能大大提高用户与机器设备、计算机部件之间的交流效率。现在采用摄像头跟踪进行手势识别的技术已经使用一段时间,但是其对硬件的要求高、分析的数据大,使得其产品相对昂贵或者识别能力不够强。与摄像头跟踪技术相比,基于无线传感器网络的手势识别速度更快,价格更便宜并且实用。通过对移动终端设计一套手势识别的算法,利用无线传感器网络实现用手机终端操作计算机的终端的一系列复杂命令。实验证明,该算法适用于大型游戏操作和平台展示,使用户不用通过购买相关硬件直接安装使用。     

基于小波包分析的虹膜识别研究

虹膜特征提取是虹膜识别中的关键环节.小波方法在提取虹膜特征时未对分解后的高频空间进一步细化分解,而虹膜纹理特征较多地蕴含在高频空间中,因此提取的虹膜特征在表示特征能力上存在不足.针对此类问题,提出一种基于小波包多尺度分解的虹膜识别方法,利用阈值将小波包分解后第二层对角高频子带图调制为虹膜特征码,利用海明距离对特征进行识别.对108类人眼虹膜图像进行特征提取与匹配,分解小波采用sym2小波,共进行5350次特征匹配,正确识别率达到98.5％,在识别性能上优于Boles的小波变换过零点法和Lim的二维Haar小波变换法,仅次于Daugman的二维Gabor方法.     

基于小波包分析的虹膜识别研究

虹膜特征提取是虹膜识别中的关键环节.小波方法在提取虹膜特征时未对分解后的高频空间进一步细化分解,而虹膜纹理特征较多地蕴含在高频空间中,因此提取的虹膜特征在表示特征能力上存在不足.针对此类问题,提出一种基于小波包多尺度分解的虹膜识别方法,利用阈值将小波包分解后第二层对角高频子带图调制为虹膜特征码,利用海明距离对特征进行识别.对108类人眼虹膜图像进行特征提取与匹配,分解小波采用sym2小波,共进行5350次特征匹配,正确识别率达到98.5％,在识别性能上优于Boles的小波变换过零点法和Lim的二维Haar小波变换法,仅次于Daugman的二维Gabor方法.     

一种数显仪表动态字符快速识别算法

在对动态仪表的数显数字字符图像识别中,将细化后的字符图像看作是一幅连通图,选择闭合曲线作为其整体特征,将笔画端点所处字符图像中子区域的位置做为主要的细节特征,对字符进行识别。试验结果表明该方案是可行的和有效的。     

全排列的递归算法实现

递归算法的设计与实现是非常重要的内容,全排列是组合数学中最常见的问题。提出了基于递归算法并通过c语言编程实现了计算机解题,实例数据表明程序非常高效。     

基于动态目标点的行为分解编队算法

多机器人编队可以分解为队形形成和队形保持控制两部分.针对多机器人编队控制任务中的队形形成问题,提出了一种基于动态目标点的行为分解编队算法.此算法是一种改进的基于行为的编队控制方法,这种控制方法的思路为,首先要求各机器人在每一时刻确定一个运动目标点,此运动目标点是根据运动过程中机器人实时的位置运算出来的,是一个动态的目标点.根据此目标点进而产生一个运动需求.再将此运动需求按照有限状态机(FSM)原理分解为不同的子行为,然后给这些子行为分别赋予不同的权值,并求出一组控制变量,最终对这组控制变量加权平均产生一个综合控制变量.仿真实验表明,该方法能快速有效地实现多机器人的编队控制.此编队算法可以有效应用于军事搜索、围捕或机器搬运等多个领域.     

A Random Base Change Algorithm for Permutation Groups

A new random base change algorithm is presented for a permutation group G acting on n points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator Rand(G) producing a random element of G with the uniform distribution and so that the time for each call to Rand (G) is bounded by some function f(n, G). The random base change algorithm has probability 1 - 1/|G| of completing in time O(f(n, G) log |G|) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering. The algorithm requires O(n log |G|) space and the data structure produced can be used to test group membership in time O(n log |G|). Since the output of this algorithm is a data structure allowing generation of random group elements in time O(n log |G|), repeated application of the random base change algorithms for different orderings of the permutation domain of G will always run in time O (n log² |G|). An earlier version of this work appeared in Cooperman and Finkelstein (1992b).