Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem

As an important tool for heuristic design of NP-hard problems, backbone analysis has become a hot spot in theoretical computer science in recent years. Due to the difficulty in the research on computa- tional complexity of the backbone, many researchers analyzed the backbone by statistic ways. Aiming to increase the backbone size which is usually very small by the existing methods, the unique optimal solution instance construction (UOSIC) is proposed for the graph bi-partitioning problem (GBP). Also, we prove by using the UOSIC that it is NP-hard to obtain the backbone, i.e. no algorithm exists to obtain the backbone of a GBP in polynomial time under the assumption that P ≠ NP. Our work expands the research area of computational complexity of the backbone. And the UOSIC provides a new way for heuristic design of NP-hard problems.     

A new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

A new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

Kernelization in Parameterized Computation： A Survey

Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.     

支持向量机中核参数选择的Max-Min方法

通过核函数技巧,定义了高维空间中两样本点之间的距离.引入异类距离平方阵,提出了一种新的选择SVM核参数准则,并给出算法,即max-min方法.该方法利用不同类的训练样本之间的距离,而不通过SVM标准样本训练寻求最优的(或有效的)核参数,避免了传统SVM在模型选择上经验性强和计算量大的不足.同时又分别以径向基核函数(RBF)和多项式函数为例进行试验,显示采用该方法的算法步骤.结合试验结果,得出关于核参数的选择问题一般在一个开集内只有有效值,不存在最优值,即是一个多目标优化问题的结论.并引用已有的实验结果充分支持我们的结论.max-min方法不仅在理论上提供了一种选择最优核参数的方法,而且对试验性选择具有指导作用.     

一类图构形的Orlik-Solomon代数及Tutte多项式

研究得到了n-秩轮图及其导出图构形的Orlik-Solomon代数的计算公式,n-秩轮图关于某条边的删除B_n以及n-秩轮图的Tutte多项式的一般表达式,并计算了n-秩轮图（n=5,6）的双变量着色多项式,举例说明图的双变量着色多项式与Tutte多项式是不相同的。     

几类特殊平面图的圈包装问题

给定一个无向连通图G，圈包装问题就是求G的边不相交圈的最大数目．此问题在一般图下是APX困难问题，在平面图下是NP困难问题．主要证明了在几类特殊的平面图下多项式时间可得到最优解．主要考虑外平面图，系列平行图和平面欧拉图这三类特殊的平面图．     

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

The main purpose of this paper is to exposit two very different, but very general, motivational schemes in the art of parameterization and a concrete example connecting them. We introduce a dynamic version of the DOMINATING SET problem and prove that it is fixed-parameter tractable（FPT）. The problem is motivated by settings where problem instances evolve. It also arises in the quest to improve a natural greedy heuristic for the DOMINATING SET problem.     

与地理相关数据的最优显示问题在多项式时间内可解

证明在一定条件下, 与地理相关数据的最优显示问题在多项式时间内可解. 通过分 析最优显示问题, 给出它的数学模型及评价标准. 并把它转化为二分图匹配问题, 给出了算 法. 这个算法可以在多项式时间内求得最优解.     

针对带约束匹配搜索的扩展Kuhn-Munkres算法

提出了扩展的Kuhn-Munkres算法,可解决带下界约束的局部匹配存在性问题,即在匹配全集的给定子集中,搜索得到一个二分图匹配满足其边权和大于给定阈值．扩展Kuhn-Munkres算法构造了一棵以Kuhn-Munkres算法中间过程为节点的搜索树,利用搜索优先级和剪枝,将算法时间复杂度降低至二分图匹配全集与给定子集差集规模的多项式函数．      

仙人掌链图的Hosoya多项式

1988年,对于连通图G,日本化学家Hosoya提出了一个基于距离的多项式,即H(G)≡H(G,x):=∑k≥0d(G,k)xk。仙人掌链图是一个具有如下性质的连通可平面图:其所有的内部面都是六边形;任意两个六边形要么无公共顶点,要么恰有一个公共顶点(邻接);任意三个六边形都没有公共顶点;任意一个六边形最多同时与两个六边形邻接。文章给出了仙人掌链图的Hosoya多项式。     

泛化的统一切比雪夫多项式核函数

针对分布稀疏、特征不明显的小样本数据回归中的属性冗余问题,基于统一切比雪夫多项式,提出了一种向量形式输入的可变正交多项式核函数——泛化的统一切比雪夫多项式核函数.新的核函数通过利用统一切比雪夫多项式的正交性和可变性扩大了函数的搜索空间,通过调整多项式阶数有效地控制了特征空间维数,从而解决了稀疏数据回归中的属性冗余问题.另外,利用Mercer定理证明了该核函数的有效性.在多组标准数据集和实际工程数据集上对核函数的性能进行了实验对比,结果证明新的核函数预测精度较高,泛化能力较好,在大多数标准数据集上的性能优于其他切比雪夫多项式核函数.     

Structural indexing for 3D solid digital library

In a very large digital library that support computer-aided collaborative design, an indexing process is crucial whenever the retrieval process has to select among many possible designs. In this paper, we address the problem of retrieving important design and engineering information by structural indexing. A design is represented by a model dependency graph, therefor, the indexing problem is to determine whether a graph is present or absent in a database of model dependency graphs. we present a novel graph indexing method using polynomial characterization of a model dependency graph and on hashing. Such an approach is able to create an high efficient 3D solid digital library for retrieving and extracting solid geometric model and engineering information.     

超图嵌入图的最小拥挤问题展望

We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion,the maximum number of paths that use any single edge in a cycle,is minimized. The Minimum Congestion Hypergraph Embedding in a Cycle problem is known to be NP-hard and its graph version,the Minimum Congestion Graph Embedding in a Cycle,is solvable in polynomial time. Furthermore,for the graph problem,a polynomial time approxima-tion scheme for the weighted version is known. For the hypergraphmodel, several approximation algorithms with a ratio of two have been previously published. A recent works on this problem reduced the approximation ratio to 1.5. We present a polynomial time approximation scheme in this paper,settling the debate regarding if the problem is polynomial time approximable     

一种支持向量聚类的快速算法

为了降低支持向量聚类(Support Vector Clustering,SVC)的运算复杂性,基于Yang等提出的邻近图法,用Merce[’核来表达Hilbert空间中的Euclidean距离,以此作为边的权重度量来生成最小生成树(Minimum Spanning Tree,MST),并只对MST的主干进行SVC连接运算．文中还定义了不相容性度量,并将其作为SVC连接运算中边的选择依据．试验证明,改进后算法的运行速度及聚类效果均优于邻近图法,特别是对大数据集的处理具有明显的优势,且具有一定的抗噪能力．     

凸二次规划基于新的核函数的大步校正原始-对偶内点算法

本文对凸二次规划提出了一种基于新的核函数的大步校正原始-对偶内点算法．这种核函数构造新的障碍函数不仅可以定义新的搜索方向，而且可以控制内迭代的过程，使得对凸二次规划提出的大步校正原始-对偶内点算法的多项式复杂性阶改善到O（√n（logn）2log（n／ε）），优于基于经典对数障碍函数的相应算法的复杂性阶．     

基于布谷鸟搜索算法参数优化的组合核极限学习机

针对单核极限学习机在泛化性能上存在一定局限性的问题, 提出将再生核函数与多项式核函数相结合, 建立一种新的组合核极限学习机模型, 使其具有全局核与局部核的优点, 并选择布谷鸟搜索算法对其参数进行优化选择. 仿真实验结果表明, 采用基于再生核的组合核函数作为极限学习机的核函数可行, 在实验数据集的多值分类和回归问题上, 与传统支持向量机及单核极限学习机相比, 该模型具有更好的泛化性能.     

数据挖掘在电力负荷坏数据智能辨识与修正中的应用

负荷历史数据由于各种原因含有一定的坏数据,在进行高精度的电力负荷预测或系统分析前必须对历史数据进行预处理.本文采用基于加权核函数的模糊C均值聚类的改进算法-WKFCM,以核诱导距离的简单两项和替代欧氏距离作为聚类目标公式的不相似性测度函数,减小了计算复杂度.对数据进行聚类之后,采用收敛速度快、模式分类能力强的超圆神经元网络数据辨识模型,并对识别出的坏数据进行修正,实例证明本文提出的数据处理模型具有较好的效果.     

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.     

计算机视觉中的图匹配方法研究综述

图匹配是计算机视觉与模式识别领域的基础而又重要的问题.它在诸多方面都有着广泛的应用.从优化角度看,图的匹配问题是一种离散组合优化问题,使得该问题本身具有NP(non-deterministic polynomial)-hard性质.因此,寻找该问题的一种有效的近似解是当前研究的重要问题.论文首先对图匹配问题的的问题表示进行了阐述,并分析了该问题求解的难点和关键点.然后,对近年来计算机视觉研究领域中提出的一些具有代表性的传统图匹配算法进行了归纳和综述.最后,探讨了图匹配的未来研究方向和研究思路.