An efficient simulated annealing algorithm for graph bisectioning

Author

Zhao, Y.C. ; Tao, L. ; Thulasiraman, K. ; Swam, M. N S

Author_Institution

Fac. of Eng. & Comput. Sci., Concordia Univ., Montreal, Que., Canada

fYear

1991

fDate

3-5 Apr 1991

Firstpage

65

Lastpage

68

Abstract

A new simulated annealing algorithm for solving the graph bisectioning problem is proposed. The authors run their simulated annealing algorithm, the Kernighan-Lin algorithm, and the Saab-Rao algorithms on the same set of random graphs with 50 to 500 nodes and compare their performances. Experiments show that their simulated annealing algorithm provides lower bisection cost than the Kernighan-Lin algorithm and the Saab-Rao algorithms for all of the graphs and their algorithm takes less running time than the other algorithms mentioned for all of the graphs with more than 100 nodes. For the simulated annealing approach, they conclude that sequential neighborhood search outperforms random neighborhood search in solving the graph bisectioning problem

Keywords

algorithm theory; graph theory; search problems; simulated annealing; Kernighan-Lin algorithm; Saab-Rao algorithms; bisection cost; graph bisectioning; nodes; random graphs; random neighborhood search; sequential neighborhood search; simulated annealing algorithm; Computational modeling; Computer science; Computer simulation; Costs; Physics; Routing; Simulated annealing; Temperature distribution; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Applied Computing, 1991., [Proceedings of the 1991] Symposium on

Conference_Location

Kansas City, MO

Print_ISBN

0-8186-2136-2

Type

conf

DOI

10.1109/SOAC.1991.143848

Filename

143848