期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到9篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
求强连通分量的几种算法的实现与分析 被引量：6
1
作者 陈燕 江克勤 《电脑知识与技术》 2011年第3X期2140-2142,共3页
有向图的强连通性是图论中的经典问题,有着很多重要的应用。该文给出了求强连通分量的Kosaraju、Tarjan和Gabow三个算法的具体实现,并对算法的效率进行了分析。
关键词 强连通分量 深度优先搜索 Kosaraju算法 Tarjan算法 Gabow算法
下载PDF
一种高效的面向动态有向图的增量强连通分量算法 被引量：6
2
作者 廖小飞 陈意诚 +3 位作者 张宇 金海 刘海坤 赵进 《中国科学：信息科学》 CSCD 北大核心 2019年第8期988-1004,共17页
强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要... 强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要高额的运行时开销来反复对整个图进行全量计算,以响应现实世界中普遍存在的动态有向图结构的频繁变化.其实,在通常情况下,动态有向图每次改变量极小(少于5%).其允许我们以增量的方式对动态有向图进行强连通分量计算,以缩短响应时间.因此,为解决此问题,本文提出了一种高效的面向动态有向图的增量强连通分量算法Incremental Strongly Connected Components Algorithm,简称Inc-SCC,通过对不必要的计算进行裁剪以减少算法的数据访问量和计算量,并利用SCC的不相交性进行并行处理以提升SCC计算效率.其次,提出了一种启发式优化方法进一步加快算法收敛速度.实验结果显示,本方法可以用于实时响应有向图持续性动态变化,并且当整个有向图的边变化比例为5%时,本方法相对于现有算法的加速比可达2.8到12倍,当整个有向图的边变化比例为0.5%时,本方法相对于现有算法的加速比可达2.9到12倍. 展开更多
关键词 强连通分量 动态有向图 增量计算 收敛 有向无环图
原文传递
L-fuzzy拓扑空间中的强连通性 被引量：1
3
作者 张耀华 燕鹏飞 《五邑大学学报（自然科学版）》 CAS 2009年第3期53-57,共5页
在L-fuzzy拓扑空间中引入了强连通的概念,证明了强连通的一些基本性质,并研究了强连通分支和乘积拓扑空间的强连通性,得到了一些好的结果.
关键词 连通空间 强连通集 强连通空间 强连通分支
下载PDF
面向短文本情感分类的特征拓扑聚合模型 被引量：3
4
作者 胡杨 冯旭鹏 +3 位作者 黄青松 付晓东 刘骊 刘利军 《中文信息学报》 CSCD 北大核心 2016年第5期28-35,共8页
由于短文本极稀疏性和特征分散的特点,短文本的情感分类效果总是不及篇章文本的情感分类,针对此问题,该文提出面向短文本情感分类的特征拓扑聚合模型。模型首先从特征点互信息,情感指向相似度,主题归属差异值三个维度整合计算情感特征... 由于短文本极稀疏性和特征分散的特点,短文本的情感分类效果总是不及篇章文本的情感分类,针对此问题,该文提出面向短文本情感分类的特征拓扑聚合模型。模型首先从特征点互信息,情感指向相似度,主题归属差异值三个维度整合计算情感特征的关联度,然后根据特征关联度建立拓扑聚合图模型,通过在图上求解强联通分量聚合高关联度情感特征,从大量未标注语料中提取相似特征对训练集特征进行补充,同时降低训练空间维度。实验将模型应用于短文本情感分类,与基准算法对比能提高分类准确率和召回率分别达0.03和0.027。验证了模型在缓解短文本极稀疏性和特征分散问题上的效果。 展开更多
关键词 短文本 情感分类 特征关联度 强联通分量 拓扑聚合
下载PDF
适用于稀疏图的基于关键点标记的可达性算法
5
作者 苗伟华 危辉 《计算机科学与探索》 CSCD 北大核心 2023年第10期2426-2434,共9页
有向图中任意两点间的可达性查询是研究各种网络问题时的一个基础操作,如在社交网络中查询两个人是否相互关注等。但随着网络规模的日益扩大,传统算法因巨大的时间或空间复杂度而变得难以被应用。因此需要根据网络结构特点针对性地使用... 有向图中任意两点间的可达性查询是研究各种网络问题时的一个基础操作,如在社交网络中查询两个人是否相互关注等。但随着网络规模的日益扩大,传统算法因巨大的时间或空间复杂度而变得难以被应用。因此需要根据网络结构特点针对性地使用合适的可达性算法。稀疏图可以看作由若干有向生成树与少量非树边组成,GRKPL算法将稀疏图中的可达性问题拆分成两部分:树上可达性问题与加入非树边后带来的影响。前一部分使用区间标记法解决;后一部分通过构造关键点集,将原图中所有的可达性查询转化为关键点集中的查询后得以解决。关键点集包括所有被非树边覆盖的节点,以及这些节点按照前序遍历的顺序排序后相邻节点之间的最近公共祖先。证明了关键点集的大小与原图中非树边的规模具有相同的数量级。最后在10个中小规模与4个大规模现实数据集上进行了测试,GRKPL在中小规模数据集上表现优异,查询处理时间相较于其他算法平均减少49.8%,空间占用平均减少65.1%。 展开更多
关键词 可达性 稀疏图 有向图 强连通 最近公共祖先 位运算
下载PDF
基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法
6
作者 程富豪 徐泰华 +2 位作者 陈建军 宋晶晶 杨习贝 《计算机科学》 CSCD 北大核心 2022年第8期97-107,共11页
强连通分量挖掘是图论中的经典问题之一,如何设计更高效率的串行强连通分量挖掘算法具有现实需求。GRSCC算法利用k步上近似和k步R相关集这两个粗糙集算子所构成的SUB-RSCC函数,可实现简单有向图中的强连通分量挖掘,而SUB-RSCC函数的调... 强连通分量挖掘是图论中的经典问题之一,如何设计更高效率的串行强连通分量挖掘算法具有现实需求。GRSCC算法利用k步上近似和k步R相关集这两个粗糙集算子所构成的SUB-RSCC函数,可实现简单有向图中的强连通分量挖掘,而SUB-RSCC函数的调用次数决定了挖掘效率。根据挖掘强连通分量时顶点间存在的相关性,GRSCC算法引入了粒化策略,减少了SUB-RSCC函数的调用次数,提高了挖掘效率。在GRSCC算法的基础上,分析发现了顶点间的另外两种强连通分量相关性,由此设计了一种新的顶点粒化策略,进而提出了一种顶点粒k步搜索方法,可更大程度地减少SUB-RSCC函数的调用次数。最后,提出了一种基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法KGRSCC。实验结果表明,相比RSCC算法、GRSCC算法和Tarjan算法,KGRSCC算法具有更好的性能。 展开更多
关键词 强连通分量 粗糙集 图论 粒化策略 顶点粒k步搜索
下载PDF
有向循环图G（n，α_1，α_2）中哈密顿圈的存在性判别及其结构
7
作者 杨启帆 《浙江大学学报（自然科学版）》 CSCD 1995年第4期397-405,共9页
本文详尽讨论了有向循环图Ｇ（ｎ，α_１，α_２）存在哈密顿圈的充分必要条件，并揭示了其中哈密顿圈的组合结构。我们还构造了一个Ｏ（ｎ３）算法，当Ｇ（ｎ，α_１，α_２）为哈密顿图时，算法可求出它的所有哈密顿圈．
关键词 有向循环图 强连通分支 哈密顿圈 存在性
下载PDF
Lω-空间的ω-强半连通性 被引量：1
8
作者 王瑜 马保国 张敏芝 《河南科学》 2012年第3期285-289,共5页
在Lω-空间中定义了ω-强半开(闭)集,引入了一种新的连通性,称之为ω-强半连通性,给出ω-强半连通分支的定义,研究了它们的一些基本性质.结果表明这种连通性保持了一般拓扑中连通性的许多类似性质.
关键词 LΩ-空间 ω-强半开(闭)集 ω-强半连通性 ω-强半连通分支
下载PDF
基于CPN的程序测试用例生成方法的研究
9
作者 郑文艳 《计算机工程与应用》 CSCD 2014年第11期39-45,共7页
采用成熟的建模仿真工具CPN tools不仅仅对程序设计语言的三种基本结构进行了建模,而且对并行程序中的并行结构也进行了建模和仿真。在不针对某些具体语言比如C语言的情况下,提出了生成测试用例的新方法,该方法对具备三种基本结构特性... 采用成熟的建模仿真工具CPN tools不仅仅对程序设计语言的三种基本结构进行了建模,而且对并行程序中的并行结构也进行了建模和仿真。在不针对某些具体语言比如C语言的情况下,提出了生成测试用例的新方法,该方法对具备三种基本结构特性的所有程序都具有普遍适用性。对具有并行结构的程序通过化简寻找测试路径。最后在生成测试用例之后,又利用CPN tools对所获得的测试用例进行选择和评价,最终确定合适的测试用例,不仅能够保证获取的测试路径是完整的而且是最优的。 展开更多
关键词 程序测试 颜色PETRI网 强连通图 测试路径 并行结构 状态空间 状态空间爆炸
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部