###
DOI:
:2014.25(S2):178-188

基于压缩的大规模图的割点求解算法
李发明,李建中,邹兆年,张冠男
(哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001)
Cut-Vertex Detection Algorithm Based on Compression on Big Graph
LI Fa-Ming,LI Jian-Zhong,ZOU Zhao-Nian,ZHANG Guan-Nan
(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 1261   Download 1439
Received:May 07, 2014    Revised:August 19, 2014
> 中文摘要: 割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.
Abstract:The detection of cut vertex is an important operation on graph. The deep-first search algorithm can solve this problem. However, the algorithm has drawback which prevents it from applying in the real-world applications. This is because of the two characteristics for today's data. One is the scale of data is huge, so it is challenging for many operations on graph. Another challenge is that the data is changeable. Because of the massive updates, the traditional algorithm must compute repeatedly according to the change, wasting a lot of time and space. The time complexity of deep first search tree is O(|V|+|E|), where |V| and |E| are number of nodes and edges of graph, so it can adapt to the first characteristic very well. But it is useless for the second characteristic. In order to solve this problem, this paper puts forward an algorithm based on compression to discovering cut vertex. The algorithm compresses the graph based on the naïve similarity on nodes. The time complexity of the algorithm is O(|E|). It discovers cut vertex on the lossless compression graph. At the same time, the algorithm maintains the updates of the nodes and edges dynamically, and updates the graph without decompression. It discovers cut vertex on the compression graph after update. These methods reduce the consumption of time and space remarkably. The compressed graph obtained by the compression algorithm in the article can be applied to other graph operations.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61133002);国家重点基础研究发展计划(973)(2012CB316202) 国家自然科学基金(61133002);国家重点基础研究发展计划(973)(2012CB316202)
Foundation items:
Reference text:

李发明,李建中,邹兆年,张冠男.基于压缩的大规模图的割点求解算法.软件学报,2014,25(S2):178-188

LI Fa-Ming,LI Jian-Zhong,ZOU Zhao-Nian,ZHANG Guan-Nan.Cut-Vertex Detection Algorithm Based on Compression on Big Graph.Journal of Software,2014,25(S2):178-188