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.     

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.     

一类二分图的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-匹配数与完美匹配数之比的顺从界.     

Matching energy of unicyclic and bicyclic graphs with a given diameter

Gutman and Wagner proposed the concept of matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let G be a simple graph of order n and be the roots of its matching polynomial. The ME of G is defined to be the sum of the absolute values of . In this article, we characterize the graphs with minimal ME among all unicyclic and bicyclic graphs with a given diameter d. © 2014 Wiley Periodicals, Inc. Complexity 21: 224–238, 2015     

4类图完美匹配数目的递推求法

本文研究了4类特殊图完美匹配数目的显式表达式.利用划分,求和,再递推的方法分别给出了图3-n Z4,2-n(2-C6),2-n(2-K4)和3-n(C4-C6)的完美匹配数目的计算公式.     

差异化需求下考虑患者预约行为的医疗服务供需匹配方法

如何根据患者的差异化需求,撮合医生与患者双方形成合理有效的医疗服务供需匹配,是医疗服务运作管理中重要的研究问题。本文针对医疗服务中医生与患者的实际需求,提出了一种考虑患者预约行为的匹配决策方法。在该方法中,首先依据患者的预约行为及特征分类;然后,通过计算不同情形下医患双方的差异度,获得了医患双方的满意度矩阵;在此基础上,提出了匹配预约患者与医生的E-HR算法,并进一步构建了匹配剩余患者和医生的多目标优化模型,通过模型求解得到最优匹配结果;最后,通过算例说明了本文提出方法的可行性和实用性。     

一类新图的匹配唯一性

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

Maximally resonant polygonal systems

A benzenoid system G is k-resonant if any set F of no more than k disjoint hexagons is a resonant pattern, i.e, G−F has a perfect matching. In 1990’s M. Zheng constructed the 3-resonant benzenoid systems and showed that they are maximally resonant, that is, they are k-resonant for all k≥1. Recently, the equivalence of 3-resonance and maximal resonance has been shown to be valid also for coronoid systems, carbon nanotubes, polyhexes in tori and Klein bottles, and fullerene graphs. So our main problem is to investigate the extent of graphs possessing this interesting property. In this paper, by replacing the above hexagons with even faces, we define k-resonance of graphs in surfaces, possibly with boundary, in a unified way. Some exceptions exist. For plane polygonal systems tessellated with polygons of even size at least six such that all inner vertices have the same degree three and the others have degree two or three, we show that such 3-resonant polygonal systems are indeed maximally resonant. They can be constructed by gluing and lapping operations on three types of basic graphs.