Please use this identifier to cite or link to this item:
Title: A modified noising algorithm for the graph partitioning problem
Authors: Sudhakar, V.
Siva Ram Murthy, C.
Keywords: Algorithms
Computational complexity
Computer simulation
Heuristic methods
Problem solving
Simulated annealing
VLSI circuits
Clique partitioning
Graph partitioning
Modified noising algorithm
Graph theory
Issue Date: 1997
Citation: Integration, the VLSI Journal, 22(Feb.), 101-113
Abstract: Many heuristics such as iterative improvement and simulated annealing are available in the literature which try to give a near-optimal solution to the graph partitioning problem. Recently, a new method called the noising method has been proposed for solving combinatorial optimization problems. The noising method has been successfully employed to solve 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 problems, viz., the clique partitioning problem using random graphs and the graph partitioning problem using concurrent VLSI circuit simulation program graphs. We compare our algorithm with the original noising and the simulated annealing algorithms. The results show that our modified 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.
ISSN: 1679260
Appears in Collections:Articles

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.