DocumentCode
3335088
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
fYear
1991
fDate
1-2 Mar 1991
Firstpage
92
Lastpage
95
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;
fLanguage
English
Publisher
ieee
Conference_Titel
VLSI, 1991. Proceedings., First Great Lakes Symposium on
Conference_Location
Kalamazoo, MI
Print_ISBN
0-8186-2170-2
Type
conf
DOI
10.1109/GLSV.1991.143948
Filename
143948
Link To Document