论文部分内容阅读
查找图的连通分量在生物信息学领域有着重要应用价值,其中的关键问题之一是查询最大连通Steiner分量(SMCC).针对已有最大连通Steiner分量查询方法中存在的查询效率低的问题,本文首先提出利用k-edge连通分量与(k+1)-edge连通分量之间的包含关系建立顶点集合的分层索引KST.和现有的专用索引相比,KST索引规模得到了缩减;然后本文提出了基于KST索引的SMCC查询算法以及具有顶点数量限制的SMCC L查询算法.和已有方法中索引的是图中顶点不同,KST索引中维护的是顶点集合的包含关系.其优点