A MODIFIED NOISING ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM

Many heuristics such as iterative improvement and simulated annealing are available in the literature which try to give a near-optimal solut ion to the graph partitioning problem. Recently, a new method called t he noising method has been proposed for solving combinatorial optimiza tion problems. The noising method has been successfully employed to so lve the clique partitioning problem. We extend the method to solve the graph partitioning problem. We also propose a modified noising method (algorithm) for efficient solution of the graph partitioning problem. We evaluate the performance of our algorithm for solving both the pro blems, viz., the clique partitioning problem using random graphs and t he graph partitioning problem using concurrent VLSI circuit simulation program graphs. We compare our algorithm with the original noising an d the simulated annealing algorithms.?he results show that our modifie d noising algorithm compares favourably with the original noising and the simulated annealing algorithms, both in terms of the run time and the quality of the solutions obtained.