循环图C2n(1,2n/3)的2-偶匹配可扩性

文章主要刻画了循环图C2n(1,2n/3)的k-偶匹配可扩性,得出对任意的n(n＞3),C2n(1,2n/3)是2-偶匹配可扩性的.     

书本图的偶匹配可扩性

该文得出的主要结论是:书本图Bm是偶匹配可扩的当且仅当书本图Bm同构于B1或者B2.并且书本图Bm是基本的.     

一个n-可扩图的充分必要条件

本文提出了一个定理并给出了详细证明,该定理给出了n-可扩图的一个充分必要条件。     

并行算法的可扩放性分析

本文讨论并行算法的可扩放性的定义，研究目的和各种评判标准，以期有助于了解并行算法和体系结构的匹配关系，最大化系统的加速和效率以及预计目前小规模并行机上的并行算法运行于巨最并行机ＭＰＣ上时的性能。     

并行SCAN算法及其可扩放性分析

SCAN算法是构成某些并行算法的一个简单而常用的基本模块。本文首先描述了SCAN操作及其串行和并行算法的设计；然后介绍了并行算法的可扩放性概念、度量及其分析方法；最后分析了不同互连结构上的并行SCAN算法的可扩放性，并用一组在Transputer阵列上的实验对分析所得的结论进行了验证。     

如何测量SMP机群可扩放性

可扩放性是并行计算的一个重要性能标准,但是传统的可扩放性准则并不适用于SMP机群.如何测量SMP机群的可扩放性?试图提出该问题的一个解决方案.首先找出并验证问题的根源--处理器集合不等价性.然后,采用处理器集合的观点来全面、正确地观察系统的行为,而并非像传统的做法那样仅仅使用处理器数来描述并行系统.通过引入性能参考因子的概念,扩展了传统的准则以适应SMP机群体系结构.实验结果显示,扩展后的度量准则适用于SMP机群,且具有较高的准确性.     

基于工作站集群环境的可扩放性度量标准

1.引言可扩放性是指并行算法有效利用可扩充的处理机数目的能力,目前已经提出了许多可扩放性度量方法,其中最典型的是:等效率方法、等平均速度方法和平均延迟方法。等效率的方法严格地说只是一种分析的方法,在实际应用中不够准确,而且该方法给出的是工作量与处理器数的关系函数,反映了工作量随处理器数变化的趋势,并没有一个量化的数据。等平均速度的方法将平均速度作为衡量可扩放性的主要指标,是一种将算法与机器相结合的基于测量的方法,但是在实际情况中很难精确地测量出程序运行的速度。平均延迟的方法使用平均计算延迟作为衡量可扩放性的主要指标,精确地考虑了算法与体系结构两者的特性,也是一种基于测量的方法,但该方法需要使用专用的硬件或者专门的系统级软件来测量并行程序运行时每个处理器上的延迟时间,因此难以广泛地应用于各种并行机上。     

大型网络中近似子图匹配研究

为降低噪声对近似子图匹配准确率的影响,提出一种改进的近似子图匹配方法。在预处理阶段,利用k-近邻顶点集为数据图中的每个顶点建立标签-权重向量索引。在查询过程中,基于单个近邻标签的权重距离和所有近邻标签的整体匹配程度进行两级过滤,生成顶点候选集,采用生成树匹配和图匹配的方式确定查询图在大型网络中的位置。在真实数据集上的实验结果表明,该方法具有较高的执行效率和匹配准确率。     

网络计算环境下并行算法及其可扩放性分析

并行算法的可扩放性是提其有效利用计算节点的能力，它可以预测算法在处理机数目变化时的性能，在网络环境下用ＰＶＭ实现了并行矩阵乘法及ＰＳＲＳ算法，分析了在网络计算环境下这两个算法的可扩放性，并利用试验数据进行了验证。     

4类图完美匹配数目的显式表达式

匹配计数理论是图论的核心内容之一,此问题有很强的物理学、计算机科学和化学背景;但是,一般图的完美匹配计数问题却是[NP-]难问题。用划分、求和、再嵌套递推的方法给出了4类图完美匹配数目的显式表达式;所给出的方法,可以计算出相同结构重复出现的许多图的所有完美匹配的数目。     

二部图的所有极大匹配

二部图作为一种非常重要的数据结构有很多特殊性质,针对文献[4]中的二部图的所有极大匹配求解算法,给出了反例证明了该算法是错误的,同时证明了二部图的所有极大匹配的求解是NP难问题.     

多部图的匹配算法研究

本文给出了一个多部图的商匹配问题的定义,提出了求解多部图商匹配问题的一个算法。该算法使用圈与割集中偶图的交相结合的方法,利用求二部图的最大匹配算法,求解多部图的最大商匹配问题。     

基于深度优先搜索的一般图匹配算法

对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O（n^3）,但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O（n＊degree（n））,degree（n）为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。     

基于赋权二部图的记录簇匹配模型及其算法

通过一组成员记录表示实体时,相似记录匹配问题被扩展为记录簇匹配问题。提出2种记录簇匹配模式,应用赋权二部图理论建立记录簇匹配数学模型,设计记录簇上下界匹配算法。快速推导出记录簇匹配阈值的上下界,以减少记录簇子记录最大权的匹配次数。实验结果证明该算法能提高记录簇匹配精度和计算效率。     

基于概念图匹配的语义相似性算法研究

本文针对传统搜索技术查全率和查准率不能满足用户日益增长的需求这一突出问题,提出一种基于概念图语义匹配的方法来计算两个本体中类之间的相似性,文中提到的本体是由实体类、这些类之间的语义关系和描述这些类的不同特征组成的.该模型首先将用户的查询信息转变为一个概念图,然后和已有的资源概念图进行匹配计算语义的相似性,实例表明该方法可以满足用户的需求,提高了检索效率.     

电子中介中的多属性匹配研究

研究了电子中介处理个人之间单件物品交易时的多属性匹配问题。建立了多目标匹配模型,推导了用理想点法求解该模型时,求解其一次距离最小等价于求解原各目标相应系数直接相加所得的单目标指派问题。用有指导随机搜索算法求解了距理想点的二次距离最小。仿真实验表明,变量规模小于65时可以求二次距离最小并得到满意解;而大于65时求一次距离最小更为合适。     

电子就业中介中的匹配研究

研究了电子就业中介中公司学生的双边匹配问题,并基于HR算法(医学院实习生与医院相互选择算法[1])建立了电子就业中介的工作流程模型。以交易双方总满意度分别最大为目标,建立了多目标指派模型,从而解决了传统HR算法的匹配公平性问题。以等权重的线性加权方法将问题化为单目标求解。仿真实验表明,该多目标算法虽不能保证匹配稳定性[2],但在匹配数量上优于HR算法。