NPAC Technical Report SCCS-477
A Collection of Graph Partitioning Algorithms: Simulated Annealing, Simulated Tempering, Kernighan Lin, Two Optional, Graph Reduction, Bisection
Gregor von Laszewski
Submitted May 01 1993
Abstract
The NP complete problem of the graph bisection is a mayor problem
occurring for example in the design of VLSI chips. This study
presents a collection of methods to find solutions to the Graph
Partitioning Problem.
The aim of the study is to compare the quality of the solutions found
with the different algorithms and the time spend to find the
solutions. We will introduce the following algorithms: