基于KST索引的最大连通Steiner分量查询算法

摘要：

查找图的连通分量在生物信息学领域有着重要应用价值,其中的关键问题之一是查询最大连通Steiner分量(SMCC).针对已有最大连通Steiner分量查询方法中存在的查询效率低的问题,本文首先提出利用k-edge连通分量与(k+1)-edge连通分量之间的包含关系建立顶点集合的分层索引KST.和现有的专用索引相比,KST索引规模得到了缩减;然后本文提出了基于KST索引的SMCC查询算法以及具有顶点数量限制的SMCCL查询算法.和已有方法中索引的是图中顶点不同,KST索引中维护的是顶点集合的包含关系.其优点在于将已有方法在遍历过程中的一次一顶点的查询方式转换为更高效的一次一集合的查询方式,显著减少了需要访问的索引点数量,极大提升了查询处理的效率;最后,基于15个真实数据集进行实验测试,从不同角度验证了本文所提方法的高效性.

关键词：无向图、k-edge连通分量、最大连通Steiner分量、索引、最大生成树

所属期刊栏目：43

分类号：TP18(自动化基础理论)

资助基金：本课题得到国家自然科学基金61472339,61572421,61873337

在线出版日期：2020-07-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1215-1229