An Overview of Kernelization Algorithms for Graph Modification Problems

Kernelization algorithms for graph modification problems are important ingredients in parameterized computation theory. In this paper, we survey the kernelization algorithms for four types of graph modification problems, which include vertex deletion problems, edge editing problems, edge deletion problems, and edge completion problems. For each type of problem, we outline typical examples together with recent results, analyze the main techniques, and provide some suggestions for future research in this field.     

非锥凸最优化问题中的可行距离

当一般的非锥凸最优化问题或其对偶不可行时, 通过引入可行距离这一概念, 讨论新系统的可行性,并考察了在新系统中可行距离的性质, 得到了与其等价的可计算的优化形式.     

量化带标公式的消解

首先引入量化带标公式,然后研究了量化带标公式的消解并且证明其健全性和拒绝完备性.另外,还引入了二元消解并证明其针对正规量化带标公式(一个量化带标公式的子集)是健全的和拒绝完备的.最后证明如果正规量化带标公式的每一个子句如果最多包含两个文字,则该公式的可满足性问题是易解的.