Simulated annealing method for clustering problem in large-scale systems

Author

Park, Chan-Ik ; Park, Kyu Ho ; Kim, Myunghwan

Author_Institution

Dept. of Electr. Eng., Korea Adv. Inst. of Sci. & Technol., Seoul, South Korea

fYear

1988

fDate

7-9 June 1988

Firstpage

2347

Lastpage

2350

Abstract

The clustering problem in large-scale systems is known to be NP-complete. The authors present an algorithm based on an iterative improvement mechanism by using the method of simulated annealing with two types of perturbations: B-move and C-move. In all test cases, their algorithm shows improved results compared to previous methods. For a real circuit example with 95 vertices and 177 edges, the algorithm produces the solution of four clusters and three bottleneck vertices while the algorithm of A. Sangiovanni-Vincentelli et al. (1977) produces the solution of five clusters and six bottleneck vertices.<>

Keywords

circuit analysis computing; large-scale systems; B-move; C-move; NP complete problem; bottleneck vertices; clustering problem; clusters; example; iterative improvement mechanism; large-scale systems; perturbations; simulated annealing; Circuit simulation; Circuit testing; Clustering algorithms; Computational modeling; Iterative methods; Large-scale systems; NP-complete problem; Partitioning algorithms; Simulated annealing; System analysis and design;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1988., IEEE International Symposium on

Conference_Location

Espoo, Finland

Type

conf

DOI

10.1109/ISCAS.1988.15414

Filename

15414