Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees

Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we assume that every job is non-preemptive. Let C={1,2,...} be a color set. A multicoloring (scheduling) F of G is to assign each job v a set of p(v) consecutive positive integers (processing consecutive time slots) in C so that any pair of adjacent vertices receive disjoint sets. Such a multicoloring is called a non-preemptive scheduling. The cost non-preemptive scheduling problem is to find an optimal multicoloring of G.

结合K均值聚类和KD-Tree搜索的快速分形编码方法

利用部分失真搜索求解传统K均值聚类算法中的最近邻搜索问题,显著地减少了传统算法的乘法次数,从而提高了聚类速度;然后用改进后的聚类算法来加速分形编码:首先将定义域块聚类并为每个类建立一棵KD-Tree,编码时对每个值域块先后用部分失真搜索与近似最近邻搜索得到与其距离最近的若干KD-Tree及其上的若干最近邻,而其最优匹配块即由后者产生.实验结果表明,相对于全局搜索,该方法能大幅度地提高编码速度和较大地提高压缩比,而解码质量只有很小的下降;相对于同类方法,在相同压缩比下有更好的加速效果和解码质量.

K_3与偏k-树乘积的树宽

图G的树宽是使图G成为1个k-树的子图的最小整数k,也可以基于“前沿分支”的观点定义树宽.若知道1个图的树宽的下界,又能构造1种标号,使其达到下界值,则此图的树宽即能确定.笔者利用这种方法确定了K3与偏k-树乘积图的树宽,给出了它的树宽表达式及达到此树宽的标号.

任意连通图与偏k-树乘积图的树宽

一个图的树宽是使图成为一个k-树的子图的最小整数k,本文考虑了顶点数为m的任意连通图G与顶点数为n的k-连通的偏k-树的乘积图的树宽,首先利用对已知结构图进行树分解的方法,确定了二者乘积图树宽下界,然后结合乘积图树宽的上界,得出了在满足顶点数n≥mk的条件下二者乘积图树宽表达式。

树与偏k-树的乘积的树宽(英文)

本文确定了一棵树与一个ｋ－连通偏ｋ－树的乘积图的树宽．其中，偏ｋ－树是一个树宽为Ｋ的图．

一个新的激活策略在偏k-树上的应用

笔者使用一个新的激活策略证明了 ,如果G是一个偏k -树 ,其色数为r=k + 1 ,缺陷度d≥ 2k + 1 ,那么 ,对这个 (r,d) -松弛竞赛染色 ,Alice有一个赢的策略。这个结果可以写为 ( 2k+ 1 ) - χg(G)≤k+ 1 ,它是文献

K-匿名隐私保护模型下的Top-k查询

数据查询问题是K-匿名隐私保护模型下数据可用性问题之一。提出一种K-匿名数据的空间数据组织方法及其索引方法;定义了两种新的查询UK-Rank和NT-Rank,UK-Rank主要应用于一些需要排序的查询,NT-Rank应用于点查询或者范围查询;采用了Monte-Carlo积分近似计算的抽样方法来提高查询效率。对提出的相关算法进行了实验,结果表明,将K-匿名数据组织成空间数据的方法是可行的,并且应用抽样方法后,查询效率大大提高。

一种KD树集成偏标记学习算法

针对样本集不均衡造成分类器精度不足的问题,提出一种KD树均衡训练集的集成偏标记学习算法。按照伪标签划分样本,采用KD树检索的方式均衡训练集,再采用多个分类器投票方式实现消岐,最终运用集成学习的方法实现分类。在公开数据集上的仿真实验结果表明,该偏标记学习算法在分类上具有较好的表现力。

基于成分数据的古代玻璃制品分析与分类

古代玻璃制品的化学成分属于成分数据,基于成分数据分析方法可以对玻璃制品的化学成分进行分析,研究其分类规律,并对未知玻璃文物鉴别其所属类型.首先,基于Spearman相关系数以及卡方检验分析玻璃文物表面风化与其类型、纹饰、颜色的关系;通过单形空间均值来分析玻璃表面有无风化化学成分含量的统计规律;构建Dirichlet回归模型来预测风化点风化前的化学成分含量.其次,构建决策树、偏最小二乘判别分析两种模型对两类玻璃进行初分类特征选择;进一步,用K-means聚类对两类玻璃进行亚分类,并通过偏最小二乘判别分析对两类玻璃进行亚分类特征选择;进而,利用所得分类规律对未知类别玻璃鉴别其所属类型.最后,运用灰色关联分析分别探究两类玻璃化学成分之间的关联关系及其差异性.