基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

新的二部图判定算法

二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂.需要指数级的时间代价.利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接.给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题.     

基于三角环的顶点着色问题解法

图的着色问题是一个NP难问题,本文着重探讨无向图的顶点的三色问题,提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解,解决了顶点三色的可满足性问题,克服了以前图遍历过程中的回溯问题,以及由此推论顶点四色和五色问题的极大独立集。     

从中序遍历及后序遍历构造二叉树

本文给出了一个算法，该算法输入一棵二叉树的中序遍历和后序遍历的结点序列，构造出该二叉树。该算法具有Ｏ（ｎ）时间复杂度，是解决该问题的最优算法，其中ｎ为二叉树的结点数。     

基于改进遍历矩阵和像素值扩散的通用图像加密算法

为了提高遍历矩阵的随机性和安全性,实现对图像信息的有效保护,提出了遍历矩阵构造的新方法,并结合像素值扩散设计了一种有效的图像加密算法。首先,利用混沌序列构造出完全不依赖载体图像灰度值的整数遍历矩阵,并利用此矩阵在图像空域进行迭代置乱,改进了传统遍历仅按特定路线扫描的局限性,以及对遍历周期和次数的过分依赖性;接着采用一个均匀分布的新混沌数列实现像素值扩散,改变了图像的统计特性,并使混沌映射不可逆;最后,构造出符合密码使用习惯的密钥生成系统,形成相对完整的加密体系,实现了图像加密。从统计特性、密钥空间、像素相关性、密钥敏感性、差分分析等多方面对算法的安全性进行了分析,结果表明,算法密钥空间大,抗攻击能力强,安全性高,实用性强。     

二叉树的遍历探究与应用

通过对同一棵二叉树的前序遍历、中序遍历、后序遍历及层次遍历得到四个不同序列的分析,概括出二叉树的前序遍历、中序遍历、后序遍历及层次遍历序列间的关系,确定对应的二叉树。     

一种有效的基于图遍历的加权序列模式挖掘算法

为解决加权遍历模式挖掘问题,概括了加权有向图的种类,提出一种边加权有向图与顶点加权有向图间的变换模型,并基于该模型提出一种基于图遍历的加权序列模式挖掘算法GTWSPMiner.该算法根据遍历模式中的项的连续性特点,采用一种加权前缀投影序列模式增长方法,将原挖掘序列数据库的任务分解成一组挖掘局部投影数据库的小任务.对比实验结果表明,该算法能快速有效地挖掘加权频繁遍历模式.     

构造二叉树算法的研究

本文介绍了由一棵二叉树的某两种遍历序列或某种遍历序列和结点的某种信息可以唯一确定该二叉树的各种可能方法。同时本文将给出基于先序序列和结点右孩子情况的构造二叉树的非递归的新算法。     

二叉树遍历的通用非递归算法

对二叉树的遍历过程进行了深入的分析,给出了求先序序列、中序序列和后序序列的通用非递归算法。该算法只需对二叉树遍历一次即可求出三种遍历序列。算法本身揭示了二又树三种遍历的内在关系。     

深度优先遍历图的非递归算法的改进

针对深度优先遍历图的非递归算法与递归算法得到的顶点访问序列不一致的问题,提出改进算法。实验结果表明,改进算法在算法时间和空间性能保持不变的情况下克服了原算法的不足。     

Depth-first search is inherently sequential

This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first visited before v in depth-first search order of G. We show that this problem, for undirected and directed graphs, is complete in deterministic polynomial time with respect to deterministic log-space reductions. This gives strong evidence that depth-first search ordering can be done neither in deterministic space (log n)^c nor in parallel time (log n)^c, for any constant c > 0.     

A note on first-order projections and games

We show how the fact that there is a first-order projection from the problem transitive closure (TC) to some other problem Ω enables us to automatically deduce that a natural game problem, , whose instances are labelled instances of Ω, is complete for PSPACE (via log-space reductions). Our analysis is strongly dependent upon the reduction from TC to Ω being a logical projection in that it fails should the reduction be, for example, a log-space reduction or a quantifier-free first-order translation.     

Construction of Simple Path Graphs in Transport Networks: II. Analysis of Graphs’ Biconnectivity

Journal of Computer and Systems Sciences International - The problem of constructing all simple paths in an undirected graph that pairwise connect vertices from the given set is interpreted as...     

基于多区域联合粒子滤波的人体运动跟踪

针对视频人体运动跟踪中的遮挡问题, 提出了一种基于多区域联合粒子滤波器的跟踪方法. 算法把人体划分为多个关键区域, 通过基于多区域无向图的联合运动模型, 构造联合粒子滤波器, 并运用区域关联的观测评估策略对目标状态进行联合预测, 从而完成遮挡情况下目标的跟踪. 实验结果表明, 与基于单区域粒子滤波的跟踪方法相比, 本文提出的算法在具有较长时间部分和全部遮挡的跟踪问题上, 取得了较好的实验结果.     

Log-space constructible universal traversal sequences for cycles of length O(n4.03)

The paper presents a simple construction of polynomial length universal traversal sequences for cycles. These universal traversal sequences are log-space (even NC¹) constructible and are of length O(n^4.03). Our result improves the previously known upper-bound O(n^4.76) for log-space constructible universal traversal sequences for cycles.     

Leader-following consensus of multi-agent systems with switching topologies and time-delays

This paper investigates the leader-following consensus problem of multi-agent systems where the leader is static and the controlling effect of each follower depends on its own state. The control protocols are proposed for two cases: i) for network with switching topologies and undirected information flow; ii) for network with directed information flow and communication time-delays. With the aid of several tools from algebraic graph, matrix theory and stability theory, the sufficient conditions guaranteeing leader-following consensus are obtained by constructing appropriate Lyapunov functions. Simulations are presented to demonstrate the effectiveness of our theoretical results.     

Computational complexity of some problems involving congruences on algebras

We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.     

覆盖组播的最小覆盖代价路由算法

与IP组播相比,覆盖组播通常会消耗更多的底层网络资源。因此,在覆盖网中构造组播转发树时,考虑合理地利用底层网络资源具有一定的实际意义。给出覆盖代价的概念,把覆盖组播路由问题归结为求无向完全图的度和延迟受限、具有最小覆盖代价的生成树问题,求解的目标是在满足应用需求和端用户主机性能要求的同时使所消耗的底层网络资源最少。给出了求解该问题的启发式遗传算法,通过仿真实验验证了该算法的有效性。     

有向黑白旅行商问题

黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形式--有向黑白旅行商问题.首先,给出了有向黑白旅行商问题的混合整数线性规划公式.与目前无向黑白旅行商问题包含指数多个约束的规划公式相比,它仅包含多项式个约束.其次,给出了一种启发式算法.实验表明,该启发式算法能够有效地求解黑白旅行商问题的实例.由于无向黑白旅行商问题是有向黑白旅行商问题的特例,故文中的结论对于求解无向黑白旅行商问题同样有效.     

The complexity of graph languages generated by hyperedge replacement

Summary Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.Parts of the results of this paper were presented at 15^th ICALP, [La88b]