An experimental evaluation of modified algorithms for the graph partitioning problem
J. Šilc, P. Korošec, B. Robič
17th International Symposium on Computer and Information Sciences (ISCIS XVII) ISCIS 2002
Orlando, FL, 28-30 October, 2002
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 behavior as a function of the graph density and the partition granularity.
BIBTEX copied to Clipboard