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.     

贴片电阻表面缺陷自动识别方法

贴片电阻生产过程中的缺陷主要依靠人工在显微镜下检测,速度慢、长期成本高、误检率高.针对贴片电阻单元具有排列整齐、结构简单、图像灰度级少的特点,在贴片电阻图像二值化、边缘提取、直线检测基础上,以相邻电阻单元的相关系数作为电阻缺陷判别依据,提出基于子图投影匹配的快速缺陷检测方法.采用主分量分析法压缩图像数据量,提取缺陷特征,以基于支持向量机对贴片电阻缺陷进行分类并建立实验系统.缺陷检测及识别实验表明,缺陷检测正确率为92.5oo,算法的快速性和识别准确度满足系统快速高精的要求.     

2.45 GHz ECR离子源的微波阻抗匹配

ECR离子源的等离子体阻抗对其微波传输与阻抗匹配设计至关重要。在中国科学院近代物理研究所现有的2.45 GHz ECR 质子源上,对等离子体阻抗进行了测量。首先用水吸收负载代替等离子体负载测量得到了所用微波窗阻抗,然后根据质子源测量数据,推算得到了等离子体阻抗。实验结果表明,脊波导输出端阻抗与后续负载不完全匹配,等离子体阻抗随微波功率变化呈非线性。这些结果为ECR离子源过渡匹配和微波窗的设计提供了参考依据。Plasma impedance of an ECR ion source is important for microwave transmission and impedance matching design. Plasma impedance was measured indirectly with the 2.45 GHz ECR proton source at the Institute of Modern Physics, Chinese Academy of Sciences. In the test, we got microwave window mpedance by using water absorption load instead of plasma load, and the source plasma impedance was derived from the test data with the 2.45 GHz ECR proton source and microwave window impedance. The experimental results show that ridge waveguide output impedance and the subsequent load does not exactly match, plasma impedance variation is nonlinear with microwave power. The achievedresult is useful in the design of ridged waveguide and microwave window.     

Search for singlet-triplet bistability or biradicaloid properties in polycyclic conjugated hydrocarbons: a valence-bond analysis

Two classes of molecules displaying singlet-triplet biradical bistability (i.e. species having significant biradicaloid properties) can be designed as follows. Alternant conjugated polycyclic hydrocarbons with numerous fixed double bonds (double bonds that remain unchanged in all its Kekulé resonance structures), a large number of Dewar resonance structures which measures the corresponding diradical resonance, and a small HOMO-LUMO band gap which measures the ease of thermal spin inversion are candidates for singlet triplet biradical bistability. Chichibabin's hydrocarbon ( 1 ) is an example. In addition, in the search for candidate molecules having singlet triplet bistability, one should also examine polycyclic conjugated systems having nonalternant induced spin frustration. Spin frustrated nonalternant polycyclic conjugated hydrocarbons will display singlet-triplet bistability (biradicaloid properties) and are generated from alternant valence-bond diradicals or Hückel molecular orbital diradicals having classical Kekulé structures by appropriate intramolecular joining of two starred or nonstarred positions with bonds, respectively.     

Dotplot: A Program for Exploring Self-Similarity in Millions of Lines of Text and Code

Abstract

An interactive program, dotplot, has been developed for browsing millions of lines of text and source code, using an approach borrowed from biology for studying homology (self-similarity) in DNA sequences. With conventional browsing tools such as a screen editor, it is difficult to identify structures that are too big to fit on the screen. In contrast, with dotplots we find that many of these structures show up as diagonals, squares, textures, and other visually recognizable features, as will be illustrated in examples selected from biology and two new application domains, text (AP news, Canadian Hansards) and source code (5ESS®). In an attempt to isolate the mechanisms that produce these features, we have synthesized similar features in dotplots of artificial sequences. We also introduce an approximation that makes the calculation of dotplots practical for use in an interactive browser.     

Optimal Pair Matching With Two Control Groups

In an effort to detect hidden biases due to failure to control for an unobserved covariate, some observational or nonrandomized studies include two control groups selected to systematically vary the unobserved covariate. Comparisons of the treated group and two control groups must, of course, control for imbalances in observed covariates. Using the three groups, we form pairs optimally matched for observed covariates—that is, we optimally construct from observational data an incomplete block design. The incomplete block design may use all available data, or it may use data selectively to produce a balanced incomplete block design, or it may be the basis for constructing a matched sample when expensive outcome information is to be collected only for sampled individuals. The problem of optimal pair matching with two control groups is shown by a series of transformations to be equivalent to a particular form of optimal nonbipartite matching, a problem for which polynomial time algorithms exist. In our examples, we implement the procedure using a nonbipartite matching algorithm due to Derigs. We illustrate the method with data from an observational study of the employment effects of the minimum wage.