An approximation algorithm for graph k-partitioning
Chao Xu, Hongmei Ge · 2012
Graph partitioning used in many fields is an important problem in graph theory so that an efficient algorithm for graph partitioning is meaningful. But graph partitioning is a NP-complete problem which is hard to obtain an optimization solution in polynomial time. This paper studies the relevant knowledge of information theory and designs an approximation optimization algorithm for solving graph K partitioning. The theory analysis and experimental results show that time complexity of the algorithm is O(V2).