检索结果-南通市图书馆

计算机学报 2004年第10期27卷 1388-1394页

作者：李光辉李晓维浙江林学院信息工程学院杭州311300 中国科学院计算技术研究所

组合验证是数字集成电路形式化设计验证的重要方面 .该文提出了一种基于增量布尔可满足性的组合等价性检验方法 ,通过合理选择候选等价结点和增量可满足性算法来提高算法性能 ,并通过对内部等价结点的置换及将等价关系转化为相应的合取... 详细信息

组合验证是数字集成电路形式化设计验证的重要方面 .该文提出了一种基于增量布尔可满足性的组合等价性检验方法 ,通过合理选择候选等价结点和增量可满足性算法来提高算法性能 ,并通过对内部等价结点的置换及将等价关系转化为相应的合取范式公式 ,避免了误判的发生 ,又能缩小验证程序的搜索空间 .针对ISCAS’85电路的实验结果表明 ,该文提出的方法比以往同类方法更快、更强健 .

关键词：增量可满足性等价性检验组合电路形式验证数字集成电路等价结点

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

子图同构问题中索引构建方法研究

子图同构问题中索引构建方法研究

引用

作者：李美云燕山大学

学位级别：硕士

子图同构查询是指在给定的数据图中搜索所有与查询图结构相同的子图。子图同构的研究在多种领域被广泛应用,例如,蛋白质相互作用分析,化合物研究,图分类,场景分析,电子电路的计算机辅助设计等等。在理论上,子图同构查询属于NP-Complete... 详细信息

子图同构查询是指在给定的数据图中搜索所有与查询图结构相同的子图。子图同构的研究在多种领域被广泛应用,例如,蛋白质相互作用分析,化合物研究,图分类,场景分析,电子电路的计算机辅助设计等等。在理论上,子图同构查询属于NP-Complete问题,但研究者在真实数据集上做了大量的工作以期在合理的时间内解决这个问题。为了进行高效的子图同构查询,需要为数据图构建相应的索引,但是现有的索引构建方法效率低、扩展性差。因此,本文针对子图同构查询中数据图的索引构建问题展开研究,具体研究内容如下。首先,通过深入分析现有的子图同构查询中数据图的索引构建方法,发现现有方法效率低、扩展性差的原因是:(1)在邻居结点中分步查找等价结点时存在冗余计算,导致效率低;(2)索引构建过程中,中间结果数据量大,导致扩展性差。其次,提出排序加验证求解等价结点的思想,并设计相应的算法gIndex BasedSV来提升等价结点查询效率。gIndex BasedSV算法将结点按照标签分组,组内排序找到具有等价关系的结点后,对于没有等价关系的结点,进一步验证其隶属的等价关系,减少了对结点的重复计算,提高了索引构建的效率。再次,提出两次排序求解等价结点的思想,并设计相应的算法gIndex BasedTS,进一步提升索引构建的效率和扩展性。gIndexBasedTS算法根据结点等价的定义,将等价结点用两种邻居信息来表示,将算法的空间复杂度降为线性。通过两次排序,gIndex BasedTS算法避免了gIndexBasedSV算法在验证阶段的高昂代价,进一步提升了索引构建的效率。最后,基于不同规模的数据集,通过实验对本文所提出的索引构建算法的效率和扩展性进行了验证。

关键词：子图同构图索引图压缩等价结点排序

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于大规模图的子图匹配算法研究

基于大规模图的子图匹配算法研究

引用

作者：王卓燕山大学

学位级别：硕士

图作为一种重要的数据结构,广泛应用于化学研究、社交网络、生物学等诸多领域的实际问题中。子图匹配作为图数据管理的一个研究热点,更是备受关注。随着数据量呈指数级增长,如何在有限的时间内完成计算机内存所能接受的图匹配过程,是研... 详细信息

图作为一种重要的数据结构,广泛应用于化学研究、社交网络、生物学等诸多领域的实际问题中。子图匹配作为图数据管理的一个研究热点,更是备受关注。随着数据量呈指数级增长,如何在有限的时间内完成计算机内存所能接受的图匹配过程,是研究者面临的挑战。现有的子图匹配算法通常采用过滤和验证策略,适用于规模较小的数据集,图数据规模的增大以及匹配过程中的冗余计算问题使得现有算法在大规模图数据集上的匹配时间复杂度较高。针对以上问题,本课题展开如下的研究:首先,针对数据图规模较大的问题,提出基于数据图的图压缩算法。根据结点的标签以及拓扑结构,预估结点局部影响值,利用结点局部影响值得出等价结点的判定顺序,通过比较结点标签及邻居结点信息判断是否为等价结点,并以此进行等价结点的划分,同属一个等价类的结点被压缩为一个超结点,最终将数据图压缩为规模较小的超图,有利于大规模图数据的存储和挖掘。其次,为了提高子图匹配算法的效率,提出基于结点编码的索引构建方式来创建图数据的索引,利用结点度的大小、属性标签、邻域标签滤波器以及结点的包含关系等过滤策略,对索引结构进行剪枝得到结点候选集。再次,根据查询图结点度及其标签,提出结点信息量的设定方法,并依此得出结点匹配验证的顺序。利用结点等价关系以及组合策略实现对匹配结果的扩充,最终完成整个子图匹配过程。最后,在不同的真实数据集上对上述算法与已有算法进行对比试验,以验证所提算法的时间效率。

关键词：数据挖掘子图匹配图压缩索引技术等价结点

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向双环网络的容错平均直径和容错直径

引用

龙岩学院学报 2016年第5期34卷 29-35页

作者：游德有谢锦山龙岩学院福建龙岩364000

利用有向双环网络G(n;r,s)的结点的对称性和L-形瓦的四个参数l,h,x,y,给出有向双环网络G(n;r,s)中有一个结点出故障时的容错直径和容错平均直径。

关键词：有向双环网络 L-形瓦容错直径容错平均直径等价结点

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：