Research on algorithm for solving maximum independent set of semi-external data of large graph data

摘要

The maximum independent set algorithm for large-scale data semi-existing data is studied and the solving method of the largest independent set problem in large-map data is mainly analyzed in this paper. The specific research contents are mainly divided into semi-external map algorithm based on Greedy heuristic strategy, semi-external map algorithm based on swap and design, and implementation of semi-external graph algorithm processing function library. Experiments on a large number of real and artificially generated data sets show that the algorithm in this paper is very efficient both in time and in space. The largest independent set obtained by the algorithm can reach more than 96% of its theoretical upper bound for most of the data.