Since graph partitioning is a global optimization problem, a number of popular global optimization algorithms have been explored. Among these are simulated annealing [87,61,79,62] and genetic algorithms (GA) [60,59,10]. These algorithms in their sequential form tend to take significantly more computational time (and more memory in the case of GA) compared to other partitioning algorithms. On the other hand they are easy to parallelize and they also have the potential to give partitions of better quality. In particular, these algorithms may be useful in fine tuning an existing partition created by a faster algorithm [79]. Besides, with these algorithms, a more complicated and accurate model, in the form of a cost function that takes into account the effect of communication cost and load balance, is usually used. It is noted that the K-L algorithm is also able to use more complicated cost functions [84]. However in order to retain the efficiency advantage of the algorithm such a cost function should be of a localized nature [84].