首页 | 本学科首页   官方微博 | 高级检索  
     

基于压缩的大规模图的割点求解算法
引用本文:李发明,李建中,邹兆年,张冠男.基于压缩的大规模图的割点求解算法[J].软件学报,2014,25(S2):178-188.
作者姓名:李发明  李建中  邹兆年  张冠男
作者单位:哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001,哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001,哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001,哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001
基金项目:国家自然科学基金(61133002);国家重点基础研究发展计划(973)(2012CB316202)
摘    要:割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.

关 键 词:割点  弱割点  深度优先搜索树  朴素相似性  压缩  动态维护
收稿时间:5/7/2014 12:00:00 AM
修稿时间:2014/8/19 0:00:00

Cut-Vertex Detection Algorithm Based on Compression on Big Graph
LI Fa-Ming,LI Jian-Zhong,ZOU Zhao-Nian and ZHANG Guan-Nan.Cut-Vertex Detection Algorithm Based on Compression on Big Graph[J].Journal of Software,2014,25(S2):178-188.
Authors:LI Fa-Ming  LI Jian-Zhong  ZOU Zhao-Nian and ZHANG Guan-Nan
Affiliation:School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China,School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China,School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China and School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
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.
Keywords:cut-vertex  weak cut-vertex  deep-first search tree  na?ve similar  compression  dynamic maintenance
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号