Modified iterative-improvement graph-partitioning algorithms
P. Korošec, J. Šilc
International Conference on Advances in the Internet Processing, Systems, and Interdisciplinary Research IPSI 2003
Sveti Stefan, Montenegro, 4-11 October, 2003
Graph partitioning problem has an important role with a wide range of applications in many different areas including numerical computation, geographical information systems, data-mining, database design, scientific simulation, and the design of VLSI circuits. By using partitioning, we are concentrating on trying to reduce the costs of designing systems and to speed up system operations. In this article we present a comparison and an evaluation of different, modified algorithms for solving the graph-partitioning problem. In particular, we focus on min-cut algorithms, simulated-annealing algorithms, tabu-search algorithms, and genetic algorithms; and experimentally determine their behaviour as a function of the graph density and the partition granularity.
BIBTEX copied to Clipboard