Thumbnail
Access Restriction
Subscribed

Author Lee, C.H. ♦ Kim, M. ♦ Park, C.I.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1990
Language English
Subject Domain (in DDC) Technology ♦ Manufacturing
Subject Keyword Partitioning algorithms ♦ Parallel processing ♦ Clustering algorithms ♦ Very large scale integration ♦ Computer science ♦ Joining processes ♦ Cost function ♦ Heuristic algorithms ♦ Data structures ♦ Computer networks
Abstract The k-way graph partitioning problem can be transformed into the maximum k-cut problem using a proposed technique of graph modification. It is possible to transform the graph partitioning problem into the max-cut problem by incorporating node size information into the edge weight. After transformation, a very simple cost function can be devised which makes the proposed algorithm more efficient than the Kernighan-Lin (K-L) algorithm (1970). The computing time per iteration of the algorithm is O(k*N/sup 2/), where N is the number of nodes in the given graph. Experimental results show that the proposed algorithm outperforms the K-L algorithm both in the quality of solutions and in the elapsed time. Also, as the difference between the sizes of the nodes increases, the performance gap between the proposed algorithm and the K-L algorithm becomes larger.
Description Author affiliation: Dept. of Electr. Eng., Korea Adv. Inst. of Sci. & Technol., Seoul, South Korea (Lee, C.H.; Kim, M.)
ISBN 0818690275
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1990-04-23
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 391.80 kB
Page Count 4
Starting Page 748
Ending Page 751


Source: IEEE Xplore Digital Library