一类二分图的k-匹配数

设G是一个具有二分类(X_1,X_2)的简单偶图,|X_1|=|X_2|=n,如果对于给定的c>0,|M(S)|≥(1+c)|S|对任意满足|S|≤n/2的S(?)X_i(i=1,2)都成立,其中N(S)是S的邻集,则称G是(n,c)-扩张图.给出了(n,c)-扩张图的k-匹配数与完美匹配数之比的顺从界.     

一类新图的匹配唯一性

利用图的匹配多项式及其最大实数根的性质证明了树T(1,1,n,2,1)及补图匹配唯一的充要条件是n≠1,2,5,8.     

Identification of stiffness, dissipation and input parameters of randomly excited non-linear systems: Capability of restricted potential models (RPM)

A dynamic identification technique in the time domain for time invariant systems under random external forces is presented. This technique is based on the use of the class of restricted potential models (RPM), which are characterized by a non-linear stiffness and a special form of damping, that is a product of the input power spectral density (PSD) matrix and the velocity gradient of a non-linear function of the total mechanical energy. By applying stochastic differential calculus and by specific analytical manipulations, some algebraic equations, depending on the response statistics and on the mechanic parameters that characterize RPM, are obtained. These equations can be used for the dynamic identification of the above mechanic parameters once the response statistics of the system to be identified are evaluated. The proposed technique allows one to identify single-degree-of-freedom or multi-degrees-of-freedom systems in the case of unmeasurable input. Further, the probabilistic characteristics of the external forces can be completely estimated in terms of PSD matrix.     

利用B样条曲线设计指纹图像滤波模板和快速指纹特征匹配算法

在指纹图像识别过程中,指纹图像的滤波去噪音二值化和指纹特征的匹配是最关键的两个部分.本文针对这两部分的算法设计进行分析和改进,介绍利用B样条造型来设计指纹滤波模板的方法和基于基准点附近的拓扑结构进行快速特征匹配的算法.并且利用改进后的指纹特征匹配算法,在样本指纹库中进行实验,结果表明该算法大大提高了指纹特征匹配的效率和准确性.     

不确定偏好序下的双边匹配博弈

针对带有不确定偏好序的双边匹配问题,现有方法大都仅注重整体收益之和,忽略了参与人的个体收益以及在交互选择中的策略运用.基于最大满意度准则,给出不确定序下的收益（满意度）矩阵的推导过程;然后,从个体理性视角,结合矩阵博弈的思想构建一种兼顾整体和个体收益的博弈匹配优化模型,并证明模型最优解满足纳什均衡.最后,进一步探讨各种策略选择及其优劣分析.     

A modern Bayesian look at the multi‐armed bandit

A multi‐armed bandit is an experiment with the goal of accumulating rewards from a payoff distribution with unknown parameters that are to be learned sequentially. This article describes a heuristic for managing multi‐armed bandits called randomized probability matching, which randomly allocates observations to arms according the Bayesian posterior probability that each arm is optimal. Advances in Bayesian computation have made randomized probability matching easy to apply to virtually any payoff distribution. This flexibility frees the experimenter to work with payoff distributions that correspond to certain classical experimental designs that have the potential to outperform methods that are ‘optimal’ in simpler contexts. I summarize the relationships between randomized probability matching and several related heuristics that have been used in the reinforcement learning literature. Copyright © 2010 John Wiley & Sons, Ltd.     

3阶幂图的广义导出匹配可扩性

A graph G is induced matching extendable if every induced matching of G is included in a perfect matching of G. A graph G is generalized induced matching extendable if every induced matching of G is included in a maximum matching of G. A graph G is claw-free, if G dose not contain any induced subgraph isomorphic to K1,3. The k-th power of G, denoted by Gu, is the graph with vertex set V（G） in which two vertices are adjacent if and only if the distance between them is at most k in G. In this paper we show that, if the maximum matchings of G and G3 have the same cardinality, then G3 is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if G is a connected claw-flee graph, then G3 is generalized induced matching extendable.     

Matching interdiction

We introduce two interdiction problems involving matchings, one dealing with edge removals and the other dealing with vertex removals. Given is an undirected graph G with positive weights on its edges. In the edge interdiction problem, every edge of G has a positive cost and the task is to remove a subset of the edges constrained to a given budget, such that the weight of a maximum matching in the resulting graph is minimized. The vertex interdiction problem is analogous to the edge interdiction problem, with the difference that vertices instead of edges are removed. Hardness results are presented for both problems under various restrictions on the weights, interdiction costs and graph classes. Furthermore, we study the approximability of the edge and vertex interdiction problem on different graph classes. Several approximation-hardness results are presented as well as two constant-factor approximations, one of them based on iterative rounding. A pseudo-polynomial algorithm for solving the edge interdiction problem on graphs with bounded treewidth is proposed which can easily be adapted to the vertex interdiction problem. The algorithm presents a general framework to apply dynamic programming for solving a large class of problems in graphs with bounded treewidth. Additionally, we present a method to transform pseudo-polynomial algorithms for the edge interdiction problem into fully polynomial approximation schemes, using a scaling and rounding technique.     

Improved induced matchings in sparse graphs

An induced matching in a graph G=(V,E) is a matching M such that (V,M) is an induced subgraph of G. Clearly, among two vertices with the same neighbourhood (called twins) at most one is matched in any induced matching, and if one of them is matched then there is another matching of the same size that matches the other vertex. Motivated by this, Kanj et al. [10] studied induced matchings in twinless graphs. They showed that any twinless planar graph contains an induced matching of size at least and that there are twinless planar graphs that do not contain an induced matching of size greater than . We improve both these bounds to , which is tight up to an additive constant. This implies that the problem of deciding whether a planar graph has an induced matching of size k has a kernel of size at most 28k. We also show for the first time that this problem is fixed parameter tractable for graphs of bounded arboricity.Kanj et al. also presented an algorithm which decides in -time whether an n-vertex planar graph contains an induced matching of size k. Our results improve the time complexity analysis of their algorithm. However, we also show a more efficient -time algorithm. Its main ingredient is a new, O^∗(4^l)-time algorithm for finding a maximum induced matching in a graph of branch width at most l.     

Recognizing near-bipartite Pfaffian graphs in polynomial time

A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e₁ and e₂ such that G−e₁−e₂ is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.