Strong matching preclusion for two-dimensional torus networks

The torus network is one of the most popular interconnection networks for massively parallel computing systems. The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. In this paper, we establish the strong matching preclusion number and classify all optimal solutions for the two-dimensional torus network with an odd number of vertices.     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

In this paper we consider the p-ary transitive reduction (TR _p ) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TR _p have been investigated before in different contexts; the best previous results are as follows:

Computations with quasiseparable polynomials and matrices

In this paper, we survey several recent results that highlight an interplay between a relatively new class of quasiseparable matrices and univariate polynomials. Quasiseparable matrices generalize two classical matrix classes, Jacobi (tridiagonal) matrices and unitary Hessenberg matrices that are known to correspond to real orthogonal polynomials and Szegö polynomials, respectively. The latter two polynomial families arise in a wide variety of applications, and their short recurrence relations are the basis for a number of efficient algorithms. For historical reasons, algorithm development is more advanced for real orthogonal polynomials. Recent variations of these algorithms tend to be valid only for the Szegö polynomials; they are analogues and not generalizations of the original algorithms.     

Hamiltonian-connected graphs

For a simple graph G, let . In this paper, we prove that if NCD(G)≥|V(G)|, then either G is Hamiltonian-connected, or G belongs to a well-characterized class of graphs. The former results by Dirac, Ore and Faudree et al. are extended.     

Region-Based Hierarchical Image Matching

This paper presents an approach to region-based hierarchical image matching, where, given two images, the goal is to identify the largest part in image 1 and its match in image 2 having the maximum similarity measure defined in terms of geometric and photometric properties of regions (e.g., area, boundary shape, and color), as well as region topology (e.g., recursive embedding of regions). To this end, each image is represented by a tree of recursively embedded regions, obtained by a multiscale segmentation algorithm. This allows us to pose image matching as the tree matching problem. To overcome imaging noise, one-to-one, many-to-one, and many-to-many node correspondences are allowed. The trees are first augmented with new nodes generated by merging adjacent sibling nodes, which produces directed acyclic graphs (DAGs). Then, transitive closures of the DAGs are constructed, and the tree matching problem reformulated as finding a bijection between the two transitive closures on DAGs, while preserving the connectivity and ancestor-descendant relationships of the original trees. The proposed approach is validated on real images showing similar objects, captured under different types of noise, including differences in lighting conditions, scales, or viewpoints, amidst limited occlusion and clutter.     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

Controllability of multi-agent systems based on agreement protocols

This paper investigates the controllability of multi-agent systems based on agreement protocols. First, for a group of single-integrator agents, the controllability is studied in a unified framework for both networks with leader-following structure and networks with undirected graph. Some new necessary/sufficient conditions for the controllability of networks of single-integrator agents are established. Second, we prove that, under the same topology and same prescribed leaders, a network of high-order dynamic agents is completely controllable if and only if so is a network of single-integrator agents. Third, how the selection of leaders and the coupling weights of graphs affect the controllability is analyzed. Finally, some numerical simulations are presented to demonstrate the effectiveness of the theoretical results.     

多部图的匹配算法研究

本文给出了一个多部图的商匹配问题的定义,提出了求解多部图商匹配问题的一个算法。该算法使用圈与割集中偶图的交相结合的方法,利用求二部图的最大匹配算法,求解多部图的最大商匹配问题。