Algorithms for graph partitioning and k-coloring

Abstract

Three combinatorial problems-graph partitioning, fixed k-coloring and graph coloring - are dealt with by several efficient heuristic algorithms. LEE, OEE and Move are algorithms modified from Kernighan-Lin``s two way uniform partitioning algorithm. First, OEE and LEE are applied to graph partitioning problem. With global information structure made for these algorithms rather than partial, we obtained generally good performances. The time analyses show that the algorithms don``t sacrifice time to get better solutions. Next, fixed k-coloring problem is introduced. It is shown that this problem can be transformed to graph partitioning problem. Those two algorithms (OEE and LEE) and some other algorithms are applied to fixed k-coloring problem. In this case, similar results were obtained. Finally, Move is applied to graph coloring problem, too. It gives better solution quality than traditional $D_{SATUR}$ algorithm.