Fast Maximal Cliques Enumeration in Sparse Graphs

In this paper, we consider the problem of generating all maximal cliques in a sparse graph in polynomial delay. Given a graph G=(V,E) with n vertices and m edges, the latest and fastest polynomial delay algorithm for sparse graphs enumerates all maximal cliques in O(Δ ⁴) time delay, where Δ is the maximum degree of vertices. However, it requires an O(n?m) preprocessing time. We improve it in two aspects. First, our algorithm does not need preprocessing. Therefore, our algorithm is a truly polynomial delay algorithm. Second, our algorithm enumerates all maximal cliques in O(Δ?H ³) time delay, where H is the so called H-value of a graph or equivalently it is the smallest integer satisfying |{v∈V∣δ(v)≥H}|≤H given δ(v) as the degree of a vertex. In real-world network data, H usually is a small value and much smaller than Δ.     

运动估计快速块匹配算法

基于块的运动估计是视频压缩国际标准中广泛采用的关键技术。在对目前运动估计快速块匹配算法研究的基础上，描述了运动估计的原理；揭示了在图像质量、搜索速度和压缩码率等方面提高算法效率时存在的3类主要问题：初始搜索点的选择、匹配准则和搜索策略；分别阐述了目前常用的解决这3类问题的方法，并进行了比较和分析；提出了对运动估计算法的一些展望。     

基于深度优先搜索的一般图匹配算法

对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O（n^3）,但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O（n＊degree（n））,degree（n）为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。     

Fast and Robust Stereo Matching Algorithms for Mining Automation

The mining environment, being complex, irregular, and time-varying, presents a challenging prospect for stereo vision. For this application, speed, reliability, and the ability to produce a dense depth map are of foremost importance. This paper evaluates a number of matching techniques for possible use in a stereo vision sensor for mining automation applications. Area-based techniques have been investigated because they have the potential to yield dense maps, are amenable to fast hardware implementation, and are suited to textured scenes. In addition, two nonparametric transforms, namely, rank and census, have been investigated. Matching algorithms using these transforms were found to have a number of clear advantages, including reliability in the presence of radiometric distortion, low computational complexity, and amenability to hardware implementation.     

基于差分矩阵的KMP图像快速匹配算法

针对KMP图像匹配方法应用于带噪声或子图与模板灰度非一致时的图像匹配中存在效率较低,匹配成功率很低的问题,提出了一种基于差分二值矩阵的KMP图像快速匹配算法。该算法先对图像矩阵进行差分求值,利用二值矩阵再进行KMP图像行匹配的方法搜索可能的匹配位置,比较这些位置的整个图像的匹配情况,从中筛选出正确的匹配位置。同时,在行匹配过程中通过记录开始的匹配位置来减少搜索空间,提高效率。实验表明,该方法有效提高了匹配速度,保证了匹配正确率。     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

随机边缘特征匹配在运动车辆跟踪算法中的应用

目标跟踪算法中往往需要有效的特征对目标进行跟踪识别。本文提出了随机边缘特征的概念,对其物理意义及匹配算法进行了阐述,并将其应用到运动车辆跟踪算法中。实验结果表明,该算法能够对序列图像中的多个运动车辆进行跟踪识别,对车辆的尺度、视角、光线及运动状态的变化等不利因素有较好的适应性。     

一种用于立体图像匹配的改进稀疏匹配算法

立体匹配有着广泛的应用前景,是计算机视觉领域的研究热点。立体匹配是立体视觉中最为关键和困难的一步,它的目标是计算标识匹配像素位置的视差图。文中提出的立体匹配算法基于置信传播（Belief Propagation,BP）。左图像首先经过非均匀采样,得到一个内容自适应的网格近似表示。算法的关键是使用基于置信传播的立体匹配算法,匹配稀疏的左图像和右图像得到稀疏视差图。通过左图像得到网格,稀疏视差图可以经过简单的插值得到稠密视差图。实验结果表明,该方法与现有稀疏立体匹配技术相比在视差图质量上平均有40％的提高。     

Distribution-Free Connectivity Testing for Sparse Graphs

We consider distribution-free property-testing of graph connectivity. In this setting of property testing, the distance between functions is measured with respect to a fixed but unknown distribution D on the domain, and the testing algorithm has an oracle access to random sampling from the domain according to this distribution D. This notion of distribution-free testing was previously defined, and testers were shown for very few properties. However, no distribution-free property testing algorithm was known for any graph property. We present the first distribution-free testing algorithms for one of the central properties in this area—graph connectivity (specifically, the problem is mainly interesting in the case of sparse graphs). We introduce three testing models for sparse graphs:

Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

Approximation Algorithms for Intersection Graphs

We study three complexity parameters that, for each vertex v, are an upper bound for the number of cliques that are sufficient to cover a subset S(v) of its neighbors. We call a graph k-perfectly groupable if S(v) consists of all neighbors, k-simplicial if S(v) consists of the neighbors with a higher number after assigning distinct numbers to all vertices, and k-perfectly orientable if S(v) consists of the endpoints of all outgoing edges from v for an orientation of all edges. These parameters measure in some sense how chordal-like a graph is—the last parameter was not previously considered in literature. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

可动态增删关键词的串匹配算法

多关键词匹配算法是网络监测和过滤系统的核心算法。这些实时系统常常要求算法能够方便快速地增加或删除若干关键词,而现有的多关键词匹配算法并不具备动态增删关键词的能力,无法满足实时系统的需要。文章对几种常用的高效的多关键词匹配算法(Advanced Aho-Corasick、Wu-Manber、SBOM)进行了改造和扩充,能够方便快速地增加或删除关键词,使得算法具有更好的适应性。     

Fast Multiplication and Sparse Structures

The applicability of fast multiplication algorithms to sparse structures is discussed. Estimates for the degree of sparseness of matrices and polynomials are given for which fast multiplication algorithms have advantages over standard multiplication algorithms in terms of the multiplicative complexity. Specifically, the Karatsuba and Strassen algorithms are studied under the assumption of the uniform distribution of zero elements.     

Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor

We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ-neighborhood of each node. For planar graphs, the cover has radius less than 16γ and degree no more than 18. For every n node graph that excludes a minor of a fixed size, we present an algorithm that yields a cover with radius no more than 4γ and degree O(logn). This is a significant improvement over previous results for planar graphs and for graphs excluding a fixed minor; in order to obtain clusters with radius O(γ), it was required to have the degree polynomial in n. Our algorithms are based on a recursive application of a basic routine called shortest-path clustering, which seems to be a novel approach to the construction of sparse covers. Since sparse covers have many applications in distributed computing, including compact routing, distributed directories, synchronizers, and Universal TSP, our improved cover construction results in improved algorithms for all these problems, for the class of graphs that exclude a fixed minor.     

Fast Minor Testing in Planar Graphs

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C _u and C _v . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming.     

入侵检测系统中的带权模式匹配算法

入侵检测系统（IDS）需要根据每个模式串的权值,计算给定主串的总权值并反馈给报警系统。传统的模式匹配算法在计算主串权值时效率低。为此,文中在Aho—Corasick算法的基础上,提出了带权模式匹配算法（WPM）及其改进算法（WPME）。算法优化了自动机的建立过程,对自动机每个节点的失配后继指针信息和匹配量信息进行预处理,从而避免了模式匹配阶段在计算主串权值时的回溯操作,降低了算法的时间复杂度。实验表明,改进后的算法具有效率高、匹配精确的特点。