包含所有固定阶数k树的一类图

图G是k树当且仅当G是一个顶点数为k+1的完全图,或者在图G中能找到度为k的点v,使得与v相邻的k个点构成的点集为团,且Gv也是一个k树。设G是一个顶点数为n的k树,其中n=pk+p+1,p≥2。本文构造了一类新的图包含G作为子图。

关于k树的谱半径

洪渊给出了谱半径最大的k树.该文进一步定义了关于k树的一个参数l(G),借之给出了谱半径达到第二大和第三大的k树.

同胚不可约k树的计数公式

由同胚不可约树得到同胚不可约k树的概念,并利用Polya计数定理得到了它的计数公式.

基于K树的搜索算法研究

为了解决对等网络系统搜索效率低下的问题,提出一种基于K值查找树的搜索算法。服务于搜索的K搜索树被构建。根据查询命中率,节点在树上从上到下排列,并且命中率和稳定性较大的节点在上层,搜索可以确定消息扩散的方向。通过缓存上层节点,建立搜索结果,使用节点索引,过热的资源复制以及为叶节点添加远程邻居等方法来提高搜索效率和平衡负载。分析和仿真结果表明,该算法能够在搜索效率较高的情况下大大减少无效信息,且搜索树的维护成本较低。

有源网络完全k树多项式的产生及其在网络分析中的应用

本文算法产生有源网络无源树边的完全k树多项式,算法时间复杂度与列写无向图全部树的改进的Minty算法相同。用该算法分析有源网络的符号函数可有效地减少对消冗余项数,同时也避免了对无源完全树边的符号鉴别问题。文章讨论了算法的合理性,并举例说明了它在网络分析中的应用。

k树的完美消除序列

弦图的完美消除序列可应用于用高斯消去法求解稀疏正定线性方程组的研究,并且弦图的完美消除序列在多个学科均有应用。本文主要研究弦图的子类——k树的完美消除序列,首先证明了k树的完美消除序列可以通过k度点来刻画。其次证明了k树Tk(n)的节点按照完美消除序列排序后满足:1);2) 。最后证明了k树完美消除序列与k树构造过程之间以互逆的方式一一对应。此外,本文也将前述证明应用于k树的识别,给出了相应的算法。

K—终端网络可靠度的二进制分枝树法

在二进制分枝树法求2-终端网络可靠度的基础上,提出了利用二进制分枝树法求K-终端网络可靠度的方法.

基于K^2树的大图存储优化研究

针对大图数据的一种表达方法——K2树,提出了相应的压缩优化算法。该算法利用带有启发式规则的DFS编码对图中所有节点进行重新编码,并通过自适应调整参数K,使得K2树能够充分利用网络中的社团结构特性,从而降低空间代价。给出了K2树的优化算法描述,并针对一系列真实网络和模拟网络进行了实验,验证了优化算法具有较好的压缩效果。

p2p计算中一种新的自组织任务调度拓扑结构——K+树

给出了p2p计算中一种新的自组织任务调度拓扑结构——K+树。K+树是L层k分支树和L?1层k分支树的组合。它的基本功能单元是由一个协调者peer、一个备份协调者peer和K个工作者peer组成。本文阐述如何从无组织的图拓扑为自组织的K+树、协调者peer如何选取工作者peer和备份协调者peer、peer之间如何实现负载平衡等关键技术。通过分析和仿真可知K+树具有高可靠性和伸缩性,并在一定条件下能有效降低任务的平均运行时间。

一种新的删除HB(k)树的结点的算法

Foster的删除HB(k)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除HB(k)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB(k)树的结点的算法相比,新算法不涉及辅助栈的使用。设n是HB(k)树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的删除HB(k)树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的删除HB(k)树的结点的算法短。新算法的空间复杂性是O(1),比Foster的删除HB(k)树的结点的算法低。

参数为k的几乎树中的染色多路割

染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广。给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小。对于参数为k的几乎树,给出了多项式时间精确算法。也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数。

密集杂波环境下基于KD树优化的DBR-RANSAC目标跟踪算法

地面战场侦察雷达存在虚假目标多、真实目标难以区分等问题。为了降低复杂环境下密集杂波的影响,形成稳定航迹,并提高雷达数据处理的实时性,文中提出一种基于K维树优化的密度聚类随机采样一致性多目标跟踪算法,降低使用批处理进行航迹起始时对大量数据进行密度聚类带来的运算负担;同时,利用相控阵雷达的波位信息对数据关联过程进行优化。仿真和试验数据验证表明:文中提出的算法在密集杂波环境下可有效提高运算效率并保持较高的跟踪性能。

基于K-D树的多维数据分布方法

系统地介绍了基于并行化k-d树的多维数据分布方法。给出了几种构造k-d树的策 略和相应算法，并从理论上分析和比较了各种策略的通信花费及其应用范围。

用K-D树实现对双模态多媒体数据库的有效查询

论文提出了一种用k-d树来查询双模态视觉听觉语音识别数据库的方法。这种方法揉合了查询地理信息系统的多维数据库和空间数据库的方法,结合双模态视觉听觉语音数据库自身的特点提出了在数据库中插入、查询和删除记录的算法。最后还对把查询多维数据的方法应用在双模态语音识别数据库领域进行了展望。

一种基于k维树的模糊C均值聚类算法

初始聚类中心的选择极大地影响了模糊C均值聚类算法的性能,一个好的初始聚类中心能显著加快算法的收敛速度和减少算法的运行时间。本文提出一种新的基于k维树的模糊C均值聚类算法。通过使用k维树的方法分割原始数据集得到多个网格,并选取网格的加权中心作为新的数据点构成一个简化的数据集,在此基础上可快速查找一组距离实际聚类中心较近的初始聚类中心,显著减少模糊C聚类算法的迭代次数。通过在16个人工数据集和一组真实图像数据上的实验结果表明,数据集的数据量较大时,在不损失聚类精确度的情况下,本算法相对于普通的模糊C均值聚类算法,收敛速度提升了近2倍,算法的运行时间也缩短到经典FCM算法的一半以下。

任意k元Huffman树的新构造

给出了一种简单而有效地构造任意k元最优Huffman树的新方法。给出了Huffman村存贮的父母一子女环结构，该结构空间利用率高，在不增加parent域的情况下，使查找父母的T（m）达到O（1），并能高效实现建立最优Huffman树和求Huffman编码的算法，无论是空间复杂度还是时间复杂度均优于传统算法，具有很强的实用性。

k元n树互联网络的2-终点可靠性研究

k元n树是一种用于大规模并行处理的高性能互联网络的拓扑结构。该文提出计算k元n树的2-终点可靠性的递归算法,其计算复杂度为O(n)。结合市场上网络元器件可靠性的实际情况,对k元n树的2-终点可靠性进行了分析。当n趋于无穷大时,计算出k元n树的2-终点可靠性的下限。

基于多重随机k维树地震搜索引擎的建立

描述了数据库的构建、利用多重随机k维树建立地震搜索引擎的过程。通过实际搜索测试,证明了利用地震搜索引擎确定震源信息的可行性,并探讨了其存在的问题及相应的改进措施。结果表明,地震搜索引擎能够自动、快速的确定震源信息,具有很强的实用性。

毛毛虫树T_(k_1,k_2,...,k_n)的优美标号

本文研究了毛毛虫树T(k1,k2,...,kn)的优美性,得到毛毛虫树的优美标号算法等结论.

基于FPFH的双向K维树最邻近距离比点云配准方法研究

为解决传统点云配准方法计算效率低、提取特征点分布稀疏和鲁棒性较弱等问题,提出了一种快速点特征直方图(FPFH)的最邻近距离比点云配准方法。先对原始点云数据进行体素降采样,对降采样过后的数据用FPFH的方法得到特征描述子,之后使用双向K维树的法向量阈值和最近邻距离比的方法进行特征提取,改变距离权重,统计更多的点对参数,剔除误配点对,加快点对搜索,使配准更加精准。引入Huber损失函数权重对刚体配准模型的目标函数进行优化,增强鲁棒性;后使用基于样本共识的方法(SAC-IA)进行初始粗配准,再用迭代最近点(ICP)点到面的方法完成精配准;为避免方法求解陷入局部极小值,采用Levenberg-Marquardt(LM)算法和奇异值分解法(SVD)交替迭代策略进行最优化。实验与ICP、SAC-IA+ICP、基于内部形状描述子(ISS)+ICP和FPFH+ICP算法相比,在无噪声情况下,所提方法在点云配准速度平均提高了31.07%、53.46%、3.09%和25.05%,比ICP和SAC-IA+ICP算法配准精度提高了一个数量级,比ISS配准精度平均提高了49.09%,在迭代次数少和精度设置较大时与FPFH+ICP方法配准精度相同,但速度比FPFH方法快。有噪声情况下,所提算法比FPFH配准算法速度上平均提高了30.53%,配准精度平均提高了15.47%,更加平滑;与ISS配准算法相比,配准精度提高了一个数量级,配准平均时间略快;ICP和SAC-IA+ICP方法配准失败,不参与比较。实验验证了所提方法可行,配准速度和精度有所提高,且鲁棒性和稳定性较好。