An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 ^k n ³) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). A preliminary version of this paper was presented at The 10th Workshop on Algorithms and Data Structures (WADS 2007). This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.     

基于DOM树和递归X—Y分割算法的Zone树模型

在分析DOM树的基础上提出一种基于DOM树和递归X—Y分割算法,可以根据网页的几何布局生成Zone树模型。描述了将Zone树模型和递归X—Y算法应用到文献数据检索的优越性,给出构建Zone树模型的算法。该模型主要用于在线文献的数据提取,具有速度快、准确性高等特点,优于目前大多数浏览器所采用的DOM树结构。     

云化SFT下的径集域与割集域的重构与研究

为了克服原有SFT体系中径集域和割集域处理具有模糊性、随机性和离散性故障数据能力不足的问题,使用云模型和SFT相结合的方法来解决该问题。首先使用云模型云化SFT特征函数,得到云化特征函数,进而云化径集域和割集域,最终得到云化径集域和云化割集域。云化径集域和云化割集域没有严格的分界线,分布区域是通过云滴表示的。若云滴表示的元件/系统故障概率小于P_b,这些云滴存在的区域即为云化径集域;反之大于P_b的云滴存在的区域为云化割集域。通过实例分析了元件X₁和系统的云化径集域和云化割集域,得到了他们适合工作的环境因素变化范围组合。分析过程和结果表明云化径集域和云化割集域能克服原始故障数据的不确定性。     

Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph $G=(V,E)$ with edge-weights $w:E\to {\mathbb{R}}_{\ge 0}$ and vertex-weights $\eta :V\to {\mathbb{R}}_{+}$ are given. The goal is to find a vertex set $S\subseteq V$ with $|S|\le t$ while minimizing $w(S,V\backslash S)/\eta (S)$, where $w(S,V\backslash S)$ is the total weight of the edges with exactly one endpoint in S and $\eta (S)={\sum }_{v\in S}\eta (v)$. For this problem, we present a $(O(\log t),1+ϵ)$ factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when $t=n^{o(1)}$. We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.     

面向多种场景的视频对象自动分割算法

针对当前应用于视频对象分割的图割方法容易在复杂环境、镜头移动、光照不稳定等场景下鲁棒性不佳的问题,提出了结合光流和图割的视频对象分割算法.主要思路是通过分析前景对象的运动信息,得到单帧图像上前景区域的先验知识,从而改善分割结果.论文首先通过光流场采集视频中动作信息,并提取出前景对象先验区域,然后结合前景和背景先验区域建立图割模型,实现前景对象分割.最后为提高算法在不同场景下的鲁棒性,本文改进了传统的测地显著性模型,并基于视频本征的时域平滑性,提出了基于混合高斯模型的动态位置模型优化机制.在两个标准数据集上的实验结果表明,所提算法与当前其他视频对象分割算法相比,降低了分割结果的错误率,有效提高了在多种场景下的鲁棒性.     

Corrected upper bounds for free-cut elimination

Free-cut elimination allows cut elimination to be carried out in the presence of non-logical axioms. Formulas in a proof are anchored provided they originate in a non-logical axiom or non-logical inference. This paper corrects and strengthens earlier upper bounds on the size of free-cut elimination. The correction requires that the notion of a free cut be modified so that a cut formula is anchored provided that all of its introductions are anchored, instead of only requiring that one of its introductions is anchored. With the correction, the originally proved size upper bounds remain unchanged. These results also apply to partial cut elimination. We also apply these bounds to elimination of cuts in propositional logic.If the non-logical inferences are closed under cut and infer only atomic formulas, then all cuts can be eliminated. This extends earlier results of Takeuti and of Negri and von Plato.     

求解VLSI 电路划分问题的混合粒子群优化算法

电路划分是VLSI物理设计过程中的一个关键阶段.该问题本质上是一个NP困难的组合优化问题.针对该问题,提出了一种带FM策略的混合粒子群优化算法.引入遗传算法的两点交叉算子和随机两点交换变异算子,保证了粒子在位置更新后依然可行;为了提高算法的局部搜索能力,将具有较强局部搜索能力的FM策略融入算法的位置更新;设计了种群多样性变异策略,提高了种群多样性,避免了易陷入局部最优的缺陷.对ISCAS89标准测试电路的仿真实验结果表明,所构造的算法是有效的.     

剪刀下的民间文化——民间剪纸的造型特点

民间剪纸是我国民间美术形式之一,有着悠久的历史。本文从剪纸的构图方法、剪纸的造型手段、剪纸的吉祥祝愿三个方面,分析剪纸的造型特点,从而体现出剪纸的造型源于原始的视觉思维方式和民间审美观念。     

On Reduction Systems Equivalent to the Non-associative Lambek Calculus with the Empty String

The article concludes a series of results on cut-rule axiomatizabilityof the Lambek calculus. It is proved that the non-associativeproduct-free Lambek calculus with the empty string (NL₀) isnot finitely axiomatizable if the only rule of inference admittedis Lambek's cut rule. The proof makes use of the (infinitely)cut-rule axiomatized calculus NC designed by the author exactlyfor that purpose.