Research On Edge Dominant Set Kernelization Algorithm In Big Data Environment

With the continuous development of computer technology,the field of computer research has entered the era of big data.How to effectively analyze problems in the big data environment and obtain valuable information from them has become a research focus.Traditional small-scale data processing algorithms have many problems when processing large-scale data.If the algorithm’s time complexity is superlinear or the algorithm’s required space is proportional to the data processing scale,using such algorithms to process large-scale data requires a lot of time or space.To avoid this situation,it is necessary to redesign algorithms suitable for large-scale data environments.Based on the big data parameter calculation model,this thesis studies the randomized algorithm for the maximum parameter matching problem of graphs in the big data environment and the kernelization algorithm for the parameterized edge domination set problem under limited computing resources.The main content includes the following points.(1)For the parameterized maximum matching problem in big data environments,this thesis proposes a randomized algorithm with a time complexity of O(N)and a space complexity of O(k~2),where N is the sum of the number of points and edges in the graph,and k is a parameter used to represent the size of the result,by introducing a universal hash function family.Firstly,the maximum matching algorithm is introduced when space complexity is not limited.Then,a universal hash function is introduced,and a universal hash function family is constructed.Based on this,a randomized maximum matching algorithm is designed.By setting the number of universal hash functions used in the algorithm,a maximum matching with k as the bound can be obtained in O(N)time complexity and O(k~2)space complexity with a probability of at least 1-εfor anyε>0.Moreover,determining whether a point in the graph exists in the matching only requires O(1)time,which can solve the problem under computing resource constraints in big data environments.This algorithm is resource-efficient and can effectively solve related problems.It is suitable for use in big data environments with limited computing resources and can improve algorithm efficiency while saving resources.(2)This thesis proposes an optimized algorithm for the parameterized edge dominating set problem in big data environments,with a time complexity of O(N)and a space complexity of O(k~3),which obtains a problem kernel of size O(k~3).Firstly,based on the proposed randomized algorithm for the parameterized maximum matching problem in this thesis,the existence of a maximum matching with 2k as the bound is determined.For graphs with such a maximum matching,the core algorithm for the parameterized edge dominating set problem for small-scale data is modified,utilizing the property that determining whether a point is in the maximum matching only requires O(1)time complexity in the randomized maximum matching algorithm.This results in a core algorithm suitable for big data environments,with improved space complexity and a problem kernel of size O(k~3),whose correctness is also proven.Compared to traditional algorithms,this algorithm is more efficient and can meet the needs of large-scale data processing,with broad application prospects.