带权无向图中反馈顶点集的固定参数枚举算法

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).     

一个基于着色和动态规划的3-维匹配问题算法

3-维匹配问题是六个经典的NP完全问题之一,在调度、分配、交通和网络流等问题方面有很强的应用.参数计算理论是近年来发展起来的研究和解决NP-难问题的新方法.针对3-维匹配问题,目前确定式参数算法的最好结果是O*(163k).本文结合着色和动态规划技术,提出了一个算法运行时间为O*(3.423k)的确定式参数算法,大大提高了算法的运行效率.     

利用直线对应计算纯旋转运动参数的一种线性方法

从单镜头序列图象确定运动刚体的3维运动参数是计算机视觉中一个重要的问题.本文提出了一个利用直线对应计算纯旋转运动参数的线性方法.在该算法中,仅用图象中直线的两个不变量.假设两帧图象中已经抽取和匹配出4对以上的对应直线,则可以唯一地确定旋转运动参数,该算法适用予旋转轴过投影中心的情况.本文同时给出了实验结果.     

稳定婚姻匹配问题的一个快速枚举算法

稳定匹配问题是算法理论中的典型问题之一,稳定婚姻匹配问题则是一种解决二部图匹配问题的模型。论文对稳定婚姻匹配问题进行了简单的阐述,并介绍了求解典型稳定婚姻问题的Gale-Shapley算法的基本思想及其性质。为了快速求出所有的稳定匹配结果,提出了基于先序遍历森林的快速枚举算法。由Gale-Shapley算法的性质得到一个定理及其推论,利用得到的推论对算法做了进一步改进和优化。在满足推论的特定条件下,提高了算法的执行效率。     

基于Hausdorff距离的3维模型匹配的改进方法

通过单目灰度图像来实现已知3维模型移动对象的精确定位，是基于3维模型的交通视觉检测与目标跟踪系统的首要环节，也是机器视觉领域的一个重要问题。为了更好地进行图像匹配，提出了一种带权值的Hausdorff距离作为3维模型投影和图像中物体轮廓相似性的测度，以避免建立图像特征与模型之间的点一点对应，这样既可减少计算量，也可提高匹配精度。为了避免陷入局部最优，可将一种带记忆功能的模拟退火(SA)算法引入图像模型匹配，这样可提高匹配参数的搜索精度。实验证明，由于SA算法和改进的Hausdorff距离相结合能有效地对3维模型和图像进行匹配，从而可对具有平移、旋转的物体实现精确定位。     

LowMC实例的差分枚举攻击效果分析

LowMC是具有低乘法复杂度特征的算法.针对低数据量和少量S盒参数下的LowMC实例,差分枚举攻击被提出,理论上可以攻击全轮LowMC算法.考虑到这种攻击是在线性层完全随机的条件下给出的,对LowMC算法在真实的线性层下抵抗差分枚举攻击的强度进行了研究.通过对关键起始轮数的研究发现,差分枚举攻击并非总是可以达到理论攻击...     

3-Set Packing参数化计数问题的复杂性及近似算法

Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。     

一种用于车间作业调度问题的智能枚举算法

车间作业调度问题是优化组合中一个著名的难题,即使规模不大的算例,优化算法的时间也很长。文章提出了一种求解车间作业调度问题的快速智能枚举算法,选取了22个标准算例作为算法的测试试验集,该算法在较短的时间内找到了17个算例的最优解,试验结果表明智能枚举算法确实是一种快速的、有效的求解车间作业调度问题的近似算法。     

利用特征点序列截断的图像匹配判决算法

当图像中特征点缺失比较严重时,利用特征点S维分配算法和K均值聚类算法的图像匹配性能较差。此外,随着待匹配图像数量的增加,上述两类算法的计算量急剧上升。针对上述问题,提出一种新的图像匹配判决算法——利用特征点序列截断的匹配判决。该算法利用了匹配特征点之间的匹配度量大于非匹配特征点之间的匹配度量,以及同一匹配簇中来源于同一图像的特征点不超过一个的先验知识,一方面对特征点缺失具有较强的鲁棒性,另一方面克服了上述两类算法中的组合爆炸问题。仿真实验证实了所提算法的有效性。     

融合2D/3D摄像机的方法与获取高精度三维视觉信息的装置

三维飞行时间摄像机可实时同步获取场景三维信息和灰度图像信息.虽然它存在图像分辨率和质量较差等问题,但它可作为二维摄像机的互补.本文借鉴立体视觉技术,提出了一种2D/3D摄像机融合的三维视觉信息获取方案.论文首先基于固定空间关系和相近视野原则,设计2D/3D立体摄像机系统对空间场景同步成像.结合三维TOF摄像机成像特性,论文借鉴立体视觉技术完成二维摄像机的高质量二维彩色图像与插补后的三维摄像机深度图像的匹配关联.因此,本方法可实现场景的高精度彩色图像和对应三维空间信息的实时同步获取,同时保留了二维摄像机的高质量彩色二维成像和三维摄像机的快速稠密三维信息获取的优势.2D/3D摄像机图像融合匹配算法复杂度低,匹配精度和准确度取决于二维摄像机和三维摄像机自身性能、摄像机标定参数精度和深度图像插补算法,不会引入新的运算误差.试验结果验证了本文算法的有效性和精确度.     

限制树宽的图的最小标记生成数算法

本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法;然后考虑了限制树宽的图,得到了效率更高的算法。该算法在树宽为常数的情况下,时间复杂度关于图的顶点个数为多项式,从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。     

Parameterized computational complexity of Dodgson and Young elections

We show that the two NP-complete problems of Dodgson Score and Young Score have differing computational complexities when the winner is close to being a Condorcet winner. On the one hand, we present an efficient fixed-parameter algorithm for determining a Condorcet winner in Dodgson elections by a minimum number of switches in the votes. On the other hand, we prove that the corresponding problem for Young elections, where one has to delete votes instead of performing switches, is W[2]-complete. In addition, we study Dodgson elections that allow ties between the candidates and give fixed-parameter tractability as well as W[2]-completeness results depending on the cost model for switching ties.     

Efficient determination of the k most vital edges for the minimum spanning tree problem

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit enumeration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.     

New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 ^k n+n ⁴). In this paper, first we present an O(3.0446 ^k n+n ⁴) fixed-parameter algorithm and an O(2.0162 ^k n ³+n ⁵) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O ^*((1+ε) ^k ) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.     

Parallel custom instruction identification for extensible processors

With the ability of customization for an application domain, extensible processors have been used more and more in embedded systems in recent years. Extensible processors customize an application domain by executing parts of application code in hardware instead of software. Determining parts of application code as custom instruction generally requires subgraph enumeration and subgraph selection. Both subgraph enumeration problem and subgraph selection problem are computationally difficult problems. Most of previous works focus on sequential algorithms for these two problems. In this paper, we present a parallel implementation of a latest subgraph enumeration algorithm based on a computer cluster. A standard ant colony optimization algorithm (ACO), a modified version of ACO with local optimum search and a parallel ACO algorithm are also proposed to solve the subgraph selection problem in this work. Experimental results show that the parallel algorithms outperform the sequential algorithms in terms of runtime or (and) quality of results. In addition, we have formally proved the upper bound on the number of feasible solutions in subgraph selection problem with or without the overlapping constraint.     

A fixed-parameter tractability result for multicommodity demand flow in trees

We study an NP-hard (and MaxSNP-hard) problem in trees—Multicommodity Demand Flow—dealing with demand flows between pairs of nodes and trying to maximize the value of the routed flows. This problem has been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial-time approximation algorithms. By way of contrast, we provide an exact dynamic programming algorithm for this problem that works well whenever some natural problem parameter is small, a reasonable assumption in several applications. More specifically, we prove fixed-parameter tractability with respect to the maximum number of the input flows at any tree node.     

顶点覆盖变体问题的确定参数可解算法研究

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题：一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。     

Drawing (Complete) Binary Tanglegrams

A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O(n ³)-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.