Graph Compression Based On Minimum Dominating Set

Nowadays,graphs in various fields are becoming larger and larger,making it easy for people to understand these large amounts of graph data is an important task in many practical applications.Graph compression is a very effective way to reduce the size and complexity of graph data.Previously,an effective graph compression method called the star-based graph compression was proposed.This method compresses a graph by shrinking a collection of disjoint subgraphs called stars.Since it is proved that compressing a graph into the optimal star-based compressed graph with the highest compression ratio is NP-complete,a greedy compression algorithm called StarZip was proposed.The compression ratio of this algorithm is approximately(ln Δ+2),where Δ is the maximum degree of the vertices in the graph.For the original graph,the effective way to solve the shortest path problem is the Dijkstra algorithm.Because the StarZip algorithm is a lossy compression,some information in the compressed graph is lost,and it is necessary to adjust the Dijkstra algorithm to solve the shortest path problem of the compressed graph.Therefore,the StarSSSP algorithm was proposed.Through experiments,StarZip and StarSSSp algorithms can effectively compress the size of the graph,and accelerate the resolution of the shortest path problem within allowable errors.This paper analyzes the rationality of the StarSSSP algorithm in the context of the StarZip algorithm,tries to find a method that minimizes the error in the results of solving the shortest path problem,and extends the two algorithms to directed graphs in an attempt to solve the shortest path problem of large-scale directed graphs.