Title :
An efficient tabu search algorithm for graph bisectioning
Author :
Tao, L. ; Zhao, Y.C. ; Thulasiraman, K. ; Swamy, M.N.S.
Author_Institution :
Fac. of Eng. & Comput. Sci., Concordia Univ., Montreal, Que., Canada
Abstract :
A new algorithm for solving the graph bisectioning problem based on tabu search is proposed. The authors run the tabu search algorithm and the Kernighan-Lin algorithm on the same set of random graphs with 50 to 500 nodes and compare their performances. They demonstrate that for all of the graphs their tabu search algorithm provides lower bisection cost than the Kernighan-Lin algorithm; and for all of the graphs with more than 200 nodes, their tabu search algorithm takes less time than the Kernighan-Lin algorithm
Keywords :
graph theory; search problems; Kernighan-Lin algorithm; bisection cost reduction; graph bisectioning; tabu search algorithm; Computational efficiency; Computer science; Costs; Iterative algorithms; Neural networks; Routing; Very large scale integration;
Conference_Titel :
VLSI, 1991. Proceedings., First Great Lakes Symposium on
Conference_Location :
Kalamazoo, MI
Print_ISBN :
0-8186-2170-2
DOI :
10.1109/GLSV.1991.143948
