Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.3, pp.359-378 (September 1993)
Clustering Algorithm for Network Partitioning
with a Hypergraph Model

Jing Lee, Jung-Hua Chou*and Shen-Li Fu
Department of Electrical Engineering
*Department of Engineering Science
National Cheng Kung University,
Tainan, Taiwan, R.O.C.

Traditional clusterig algorithms usually use a graph structure to model electrical networks. However, because of edge exaggeration, the graph model cannot exactly represent a net that interconnects more than two electrical components. The transformation from an electrical network to a graph usually induces some traps and leads the clustering procedure to grow along the nets of large size. Previous authors have usually used weighting functions to modify edge exaggeration. This strategy can decrease the intensity of traps from nets of large size but always makes new traps from small-sized nets. This paper describes a new clustering algorithm, which is based on a hypergraph model. It is different from previous algorithms, which used either graph models or weighted graph models. The hypergraph model can exactly represent electrical networks, and no distortion is induced in the transformation from the network to its corresponding hypergraph. The clustering procedure includes seed generation, candidate vertex selection, merging cluster selection, and the merging of the candidate vertex with the merged cluster. At any stage, some heuristic rules are used to guied the procedure. Computational results show that the crossing count obtained by the present algorithm is as much as 53% better than the result from a graph model, and about 21%~36% better than the results from weighted graph models. Time complexity analysis proves that the algorithm requires O(M2) time in the worst case, where M is the vertex number of a hypergraph. Real running time test show that only O(M1.73) time is actually required.

Keywords: clustering algorithm, network partitioning, cost function, complexity analysis, seed generator

Received September 1, 1991; revised May 17, 1993.
Communicated by Y. S. Kuo.