网格参数化研究进展

网格参数化是计算机图形学和数字几何处理的基本工具,有着广泛的应用背景.对网格参数化的研究进展进行了综述,主要从参数域和参数化质量两个方面介绍了网格参数化的研究现状.根据参数域的不同,讨论了平面参数化、基网格参数化、球面参数化以及曲面间的交叉参数化;根据参数化质量的不同,介绍了保长度的参数化、保特征的参数化以及致力于参数域简单的参数化.对参数化进行了分类介绍和讨论分析,概括介绍了每类方法的主要思想,讨论了每类方法的主要特性,对其中一些方法进行了比较分析,并对参数化方法存在的难点问题和未来可能的研究方向进行了总结,以期对参数化的研究进展有全面的了解.     

神经网络模型压缩方法综述

深度神经网络模型被广泛应用在图像分类、物体检测等机器视觉任务中,并取得了巨大成功。然而,由于存储空间和功耗的限制,神经网络模型在嵌入式设备上的存储与计算仍然是一个巨大的挑战。模型压缩作为一种有效的解决方法,受到了越来越多研究者的关注。首先针对卷积神经网络模型进行了研究,分析了模型中存在的冗余信息;随后对国内外学者在神经网络模型压缩方面的研究成果整理,从参数剪枝,权重共享和权重矩阵分解等方面总结了神经网络压缩的主要方法;最后针对神经网络模型发展现状及目前面临的若干主要问题进行了讨论,指出了下一步的研究方向。     

关于模糊系统辨识近年来的研究与发展

为了实现理想的模糊控制，基于对象的模糊系统辨识研究具有非常重要的理论与实际应用价值．本文主要从模糊系统结构辨识和参数辨识两方面讨论了近年来在该领域的一些研究内容和方法，分析了它们的主要优缺点并探讨了这一研究领域目前存在的问题和研究趋势．     

CAGD中参数曲面的光滑拼接研究

参数曲面作为CAGD中形状数学描述的标准形式一直受到关注,而参数曲面的光滑拼接作为实现复杂客体几何造型的重要手段一直是该领域的一个热点和难点问题.以不同参数域的参数曲面为线索,对常用的矩形域和三角域参数曲面的GC1光滑拼接的条件进行了分析,同时对这些条件在实际应用中的一些问题进行了讨论,最后对曲面光滑拼接中一些令人关注问题进行了展望.     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用.随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT).介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展.最后,提出了该问题的进一步研究方向.     

基于稀缺数据集下BN参数学习的目标识别

针对贝叶斯网络（BN）在目标识别参数建模中常常面临特征数据样本相对稀缺的问题,研究了将稀缺数据集与定性专家经验相融合来估算BN模型参数的方法——CSDE,并据此提出了一种目标识别算法。该算法在BN结构已知的情况下,将定性专家经验转化为BN条件概率之间的约束集合;随后引入凸优化求解方法完成BN目标识别模型参数的估算。在实验研究中,先通过对经典的BN模型的参数学习问题验证了CSDE算法的有效性;随后,针对实际稀缺样本数据集目标识别问题,进行了建模及识别实验。实验结果表明：所提出的算法能够较好地解决样本数据集相对稀缺条件下的目标识别参数建模问题。     

中亚语言自然语言处理综述

该文对中亚地区属于同一个语族的土耳其语、哈萨克语等诸语言的自然语言处理现状进行了综述。首先分别回顾土耳其语、哈萨克语和其他中亚语言在词法分析、句法分析、命名实体识别、机器翻译方面的研究进展,随后讨论了与具体语言无关的黏着语词法分析方面的研究情况,最后指出国内外中亚诸语言处理自然语言领域中所面临的问题和挑战,并对未来的研究提出了建议。     

测试集自动生成方法中的可执行化研究

自动生成的测试集是可执行的才具有实用意义。讨论了在测试集自动生成系统TUGEN中实现的参数化可执行化算法。分析了该算法的效果,不足及其原因;讨论了可执行化处理中所涉及谓词可满足性问题的复杂度和测试路径可执行性问题,并在此基础上进一步提出并实现了“可执行参数”的算法,克服了前一算法的不足,提高了TUGEN的实用性和执行效率,在进行了讨论分析后,以实例进行了对比和说明,并对今后的研究方向进行了展望。     

感性工学中的参数化设计方法关键技术研究现状与展望

 感性工学(KE)是将消费者感性体验融入设计中的常用方法。过去十余年间,国内 外学者对 KE 展开了研究并取得了一定成果。通过对国内外 KE 中的参数化设计方法关键技术 研究成果进行梳理,首先总结了 KE 中常用的感性意象与产品特征参数化方法;随后重点介绍 了 3 种 KE 模型构建问题上的常用方法及其特点,并将现有研究进行了对比;最后讨论了 KE 现存问题并对未来可能的研究趋势进行了展望。     

Confronting intractability via parameters

One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computational tasks. Almost no computational tasks in real life are specified by their size alone. It is not hard to imagine that some parameters contribute more intractability than others and it seems reasonable to develop a theory of computational complexity which seeks to exploit this fact. Such a theory should be able to address the needs of practitioners in algorithmics. The last twenty years have seen the development of such a theory. This theory has a large number of successes in terms of a rich collection of algorithmic techniques, both practical and theoretical, and a fine-grained intractability theory. Whilst the theory has been widely used in a number of areas of applications including computational biology, linguistics, VLSI design, learning theory and many others, knowledge of the area is highly varied. We hope that this article will show the basic theory and point at the wide array of techniques available. Naturally the treatment is condensed, and the reader who wants more should go to the texts of Downey and Fellows (1999) [2], Flum and Grohe (2006) [59], Niedermeier (2006) [28], and the upcoming undergraduate text (Downey and Fellows 2012) [278].     

Using Nondeterminism to Design Efficient Deterministic Algorithms

In this paper we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives a parameterized algorithm of running time O((5.7 k)^k n) for the 3-D matching problem, which significantly improves the previous algorithm by Downey et al. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.     

On miniaturized problems in parameterized complexity theory

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t]$\mathrm{W}[t]$ lies in W[t]$\mathrm{W}[t]$, too. In particular, the miniaturization of the dominating set problem is in W[2]$\mathrm{W}[2]$. Furthermore, we investigate the relation between f(k)·n^o(k)$f(k)·n^{\mathrm{o}(k)}$ time and subexponential time algorithms for the dominating set problem and for the clique problem.     

Parameterized analysis and crossing minimization problems

In this survey/introductory article, we first present the basics of the field of Parameterized Complexity, made accessible to readers without background on the subject. Afterwards, we survey some central questions in Graph Drawing that concern the analysis of crossing minimization problems from the viewpoint of parameterized analysis, as well as put forward some of the remaining challenges. This article originated from an invited talk given at the 29th International Symposium on Graph Drawing and Network Visualization.     

Parameterized approximation of dominating set problems

A problem open for many years is whether there is an FPT algorithm that given a graph G and parameter k, either: (1) determines that G has no k-Dominating Set, or (2) produces a dominating set of size at most g(k), where g(k) is some fixed function of k. Such an outcome is termed an FPT approximation algorithm. We describe some results that begin to provide some answers. We show that there is no such FPT algorithm for g(k) of the form k+c (where c is a fixed constant, termed an additive FPT approximation), unless FPT=W[2]. We answer the analogous problem completely for the related Independent Dominating Set (IDS) problem, showing that IDS does not admit an FPT approximation algorithm, for any g(k), unless FPT=W[2].     

Block-graph width

Let G be a class of graphs. A graph G has G-width k if there are k independent sets N₁,…,N_k in G such that G can be embedded into a graph H∈G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N_i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained.     

A fixed-parameter tractable algorithm for matrix domination

Matrix domination is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time .     

Even faster parameterized cluster deletion and cluster editing

Cluster Deletion and Cluster Editing ask to transform a graph by at most k edge deletions or edge edits, respectively, into a cluster graph, i.e., disjoint union of cliques. Equivalently, a cluster graph has no conflict triples, i.e., two incident edges without a transitive edge. We solve the two problems in time O^?(k^1.415) and O^?(k^1.76), respectively. These results round off our earlier work by considerably improved time bounds. For Cluster Deletion we use a technique that cuts away small connected components that do no longer contribute to the exponential part of the time complexity. As this idea is simple and versatile, it may lead to improvements for several other parameterized graph problems. The improvement for Cluster Editing is achieved by using the full power of an earlier structure theorem for graphs where no edge is in three conflict triples.