基于压缩的图的零漏包率割点求解算法

Cut-vertex Discovery on Graph with 0-drain Package based on Compression

随着需求的增大,数据规模迅速增长。同样在图的应用方面,图的规模也呈爆炸性增长,这样,图上的相关操作也因为图的规模巨大而变得异常艰难,这就需要研究者们提出新的方法来减少图上操作的难度。割点的查询是图的一个重要操作,提出了一种新的基于压缩的割点求解算法,在压缩的图上迅速确定原图上是否存在割点,若存在割点则返回全部可能割点,不会漏掉任何一个割点。同时,由于任何图应用中都会存在图的维护,提出一种在压缩图上进行增量维护的算法,避免了重新的计算,经过一次压缩后,压缩图可以永久使用。

With the increasing of requirement,the size of data grows very fast. In the application of graph,the size of graph is growing explosively at the same time. So,the operation on graph becomes more and more difficult because of the large size. The researchers should come up with some new ways to reduce the difficulty of operation. The query of cut vertex is an important operation on graph,so the paper puts forward a new algorithm on discovering cut vertex. By using the compressing graph,the result can be confirmed whether there is cut vertices on the original graph quickly. If there are cut vertices,algorithm outputs all the possible cut vertices without dropping any cut vertices. It has been known that any application on graph exists the problem of maintenance. The paper also puts forward an algorithm maintaining the graph incrementally. The algorithm avoid recomputing. The graph can be used forever after compressing.