图模型匹配:一种新的凹松弛函数及算法

将问题中的置换矩阵放松为双随机矩阵是近年来近似图匹配算法的一个重要发展方向. 它的本质在于将离散的图匹配问题转换成一个连续优化问题,而一般来讲, 相对于离散优化,连续优化问题的近似求解将更为容易. 但随之带来的一个问题是如何有效地将连续优化得到的双随机矩阵重新映射回一个置换矩阵. 最近文献中提出了一种针对于无向无自环图的凹松弛(Concave relaxation)函数,使得算法中的双随机矩阵可以平滑地收敛到一个置换矩阵, 并得到优异的匹配精度.但除了无向且无自环图,文献中还没有针对其他类型图模型的凹松弛函数. 本文提出一种针对于有向无自环图匹配问题的凹松弛函数, 并在此基础上给出一种图匹配算法.大量对比实验验证了本文提出模型及算法的有效性.     

A dynamical systems approach to weighted graph matching

Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems.     

Migration of Tasks in Interconnection Networks Based on the Star Graph

The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The procedure for task allocation in the star graph can be done using the star code and the allocation tree constructed based on this code. In this paper, the optimal set of codes which can collectively recognize a set of distinct substars is derived. It is shown that using only (n − 1) codes, almost half of the existing substars in an n-dimensional star is recognizable for n ≤ 9. When relinquishment of tasks is considered, task migration could potentially improve the utilization of network resources by reducing/eliminating the fragmentation caused as a result of task deallocation. A deadlock-free procedure is presented to migrate a task, distributed over the nodes of one substar, to the nodes of the other substar wherein: (i) subtasks travel in parallel via disjoint paths; (ii) the adjacency among the mapped nodes is preserved. The procedure can be made distributed with a slight modification. The work can be extended to other hierarchical networks based on permutation group.     

基于图模型的多边形自动并行构建算法

目前GIS基础算法并行化成为高性能GIS进一步深入的前提,作为GIS空间分析基础算法的重点,有必要对多边形构建提出一种自动并行算法。为此,提出基于图模型的多边形自动并行构建算法。该算法根据图模型中有向闭合环的特点对一组线段的集合进行多边形构建,能有效提高多边形构建的自动化程度。将搜索、排序等耗时较多的操作进行并行化处理,能有效减少全局搜索次数及整体排序和逻辑操作时间。实验表明,在对大规模线性数据生成区域时,该算法能有效地实现效率提升,达到良好的效果。     

图像的排列变换

任何一幅图像的直方图都可以看作是一个多重集合，该多重集由多种可重复使用的颜色组成，而具有该直方图的任意一幅图像就是该多重集上的一个全排列。因此，可以借助于集合论和群论中的一些理论和方法来研究图像的某些性质。本文首先从多重集和置换群的角度讨论了图像和排列之间的相互关系，然后作为应用实例介绍了两种基于排列变换的图像生成方法。     

Linear structure of bipartite permutation graphs and the longest path problem

The class of bipartite permutation graphs is the intersection of two well known graph classes: bipartite graphs and permutation graphs. A complete bipartite decomposition of a bipartite permutation graph is proposed in this note. The decomposition gives a linear structure of bipartite permutation graphs, and it can be obtained in O(n) time, where n is the number of vertices. As an application of the decomposition, we show an O(n) time and space algorithm for finding a longest path in a bipartite permutation graph.     

MAX^＋公式的结构特征

改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合。改名技术在简化一些难例公式的消解证明和构造高效的可满足算法方面有重要意义。MAX^＋公式是MU公式中的一个重要子类,该类公式可以通过递归的方式产生。通过分析MAX^＋公式的结构,得到了一些关于此类公式的结构特点,对进一步研究这类公式的改名问题有较大意义。     

Operations on permutations and representation in graph form

Two operations on permutations are defined and some of their properties are illustrated. A particular graph is defined as representation of the permutation set under such operations; this graph consists of strongly connected components only, having at most eight vertices.     

等价关系矩阵的置换合同性质与标准形计算

等价关系在网络分析、图论、模式识别和数据库技术等方面都有许多应用,而任意等价关系矩阵都置换合同于块1-对角矩阵标准形,从置换运算的角度分析置换合同的几条性质,提出基于图的深度优先搜索策略的置换矩阵构造算法：根据等价矩阵关系图搜索路径的性质,将图的深度优先搜索所得顶点路径与初始顶点顺序对比构造置换映射。利用置换分解原理,将置换映射分解成相应的对换乘积,得到最终置换矩阵,完成等价关系矩阵的置换相似判定。为了验证该算法的正确性和效率,设计了一个等价关系矩阵的自动生成算法。实验结果表明,置换矩阵构造算法和等价关系矩阵的自动生成算法简洁且易于理解和实现。     

支持动态图数据的子图查询方法

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。     

基于概率图的三支决策模型研究

概率图模型是一类用图形模式表达基于概率关系的模型的总称,用该模型解决损失代价问题已成为当前的研究热点。结合概率图和三支决策理论,提出了基于概率图的三支决策模型。该模型通过对数据进行分析,构造其Bayes网络;并根据模型中节点的相互依赖关系,计算出条件概率分布函数;结合查询变量的先验概率和三支决策损失代价函数,建立了相应的决策规则,给出了概率推理决策中代价最小化问题的一种解决方法。最后通过教学评估实例验证了该模型的有效性。     

一类完全非线性S-盒的构造

完全非线性S-盒在对称密码中有着重要的运用。给出有限域上完全非线性S-盒的一种构造方法。与在向量空间上构造的方法比,有限域上置换多项式的代数次数等性质更容易研究。该方法可以构造多类完全非线性S-盒,例如,通过选择幂函数形式的置换α^x,得到Satoh等人构造的S-盒;通过选取指数形式的置换x^d,所得完全非线性S-盒的分量函数的任意非零线性组合的代数次数达到最高。     

基于支撑向量置换核函数的一种领域知识与模型融合的技术

提出了一种修正撑向量核函数的理论与方法，与传统的方法相比，置换核函数的引入为领域知识与学习模型的融合提供了理论基础与方法。该文借助于置换的概念，对关于事物模式组成的不变性常识进行了形式化，求取了可以定量表述事物模式扰动的置换变换矩阵；在分类不变性的约束下，运用置换变换矩阵对核函数进行修正，获得了改进的学习模型，文本分类的实验表明，学习算法将文本领域内的知识有效地融合到了学习模型中，获得了更高的分辨率与泛化能力。     

基于表情相似性的人脸表情流形

在图嵌入(graph embedding)的框架下提出一种根据表情相似度构建邻接权重图的方法来学习人脸表情子空间.数据集中人脸图像的表情以半监督-学习的方式来估计,人脸图像之间的表情相似性由表情模糊隶属度矢量之间的内积来度量,与个体、光照、姿态等人脸差异无关.在得到的子空间内,相似表情的人脸图像位于流形上的邻近位置,表情数据在子空间内按语义的分布很好地揭示了表情模糊、演变的特性.在Cohn-Kanade人脸表情数据库和实验室自行采集的人脸表情数据集上的实验结果说明了该方法的有效性.因此,该方法可以很好地应用于各种基于人脸表情识别的人机交互中.     

The Minimum Weight Dominating Set Problem for Permutation Graphs Is in NC

In this paper, we show that the problem of finding a minimum weight dominating set in a permutation graph, where a positive weight is assigned to each vertex, is in NC by presenting an O(log n) parallel algorithm with polynomially many processors on the CRCW model.     

A Path Following Algorithm for the Graph Matching Problem

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.     

Time-varying contour topology

The contour tree has been used to compute the topology of isosurfaces, generate a minimal seed set for accelerated isosurface extraction, and provide a user interface to segment individual contour components in a scalar field. In this paper, we extend the benefits of the contour tree to time-varying data visualization. We define temporal correspondence of contour components and describe an algorithm to compute the correspondence information in time-dependent contour trees. A graph representing the topology changes of time-varying isosurfaces is constructed in real-time for any selected isovalue using the precomputed correspondence information. Quantitative properties, such as surface area and volume of contour components, are computed and labeled on the graph. This topology change graph helps users to detect significant topological and geometric changes in time-varying isosurfaces. The graph is also used as an interactive user interface to segment, track, and visualize the evolution of any selected contour components over time.     

Subcomplete generalizations of graph isomorphism

We present eight group-theoretic problems in NP one of which is a reformulation of graph isomorphism. We give technical evidence that none of the problems is NP-complete, and give polynomial time reductions among the problems. There is a good possibility that seven of these problems are harder than graph isomorphism (relative to polynomial time reduction), so that they might be examples of natural problems of intermediate difficulty, situated properly between the class of NP-complete problems and the class P of problems decidable in deterministic polynomial time. Because of strong structural similarity, two of the apparently harder problems can be interpreted as generalized isomorphism and generalized automorphism, respectively. Whether these problems ultimately prove to be harder than graph isomorphism seems to depend, in part, on the open problem whether every permutation group of degree n arises as the automorphism group of a combinatorial structure of size polynomial in n. Finally, we give an O(n² · k) algorithm for constructing the centralizer of a permutation group of degree n presented by a generating set of k permutations. Note that we may assume that k is O(n · log n), without loss of generality. This problem is a special case of one of the harder group-theoretic problems. From the method of constructing the centralizer, we recover results about the group-theoretic structure of the centralizer. Furthermore, applying our algorithm for intersecting with a normalizing permutation group, we show how to find the center of a permutation group of degree n in O(n⁶) steps, having constructed the centralizer of the group first.     

Graph colouring approaches for a satellite range scheduling problem

A goal of this paper is to efficiently adapt the best ingredients of the graph colouring techniques to an NP-hard satellite range scheduling problem, called MuRRSP. We propose two new heuristics for the MuRRSP, where as many jobs as possible have to be scheduled on several resources, while respecting time and capacity constraints. In the permutation solution space, which is widely used by other researchers, a solution is represented by a permutation of the jobs, and a schedule builder is needed to generate and evaluate a feasible schedule from the permutation. On the contrary, our heuristics are based on the solution space which contains all the feasible schedules. Based on the similarities between the graph colouring problem and the MuRRSP, we show that the latter solution space has significant advantages. A tabu search and an adaptive memory algorithms are designed to tackle the MuRRSP. These heuristics are derived from efficient graph colouring methods. Numerical experiments, performed on large, realistic, and challenging instances, showed that our heuristics are very competitive, robust, and outperform algorithms based on the permutation solution space.     

Maximum gap labelings of graphs

Given a graph, we define a base set to be a set of integers of size equal to the number of vertices in the graph. Given a graph and a base set, a labeling of the graph from the base set is an assignment of distinct integers from the base set to the vertices of the graph. The gap of an edge in a labeled graph is the absolute value of the difference between the labels of its endpoints. The gap of a labeled graph is the sum of the gaps of its edges.The maximum gap graph labeling problem takes as input a graph and a base set and maximizes the gap of the graph over all possible labelings from the base set. We show that this problem is NP-complete even when the base set is restricted to consecutive integers. We also show that this restricted case has polynomial time approximations that achieve a factor of 2/3 for trees, of 1/2 for bipartite graphs, and of 1/4 for general graphs, with a deterministic algorithm, while an expected factor of 1/3 for general graphs is achieved with a randomized algorithm. The case of general base sets is approximated within an expected factor of 1/16 for general graphs with a randomized polynomial time algorithm. We finally give a polynomial time algorithm that solves the maximum gap graph labeling problem for a graph that has bounded degree and bounded treewidth. The maximum graph labeling problem shows connections with the graceful tree conjecture.