A k-way graph partitioning algorithm based on clustering by eigenvector
SCIE
SCOPUS
- Title
- A k-way graph partitioning algorithm based on clustering by eigenvector
- Authors
- Choe, TY; Park, CI
- Date Issued
- 2004-01
- Publisher
- SPRINGER-VERLAG BERLIN
- Abstract
- The recursive spectral bisection for the k-way graph partition has been underestimated because it tries to balance the bipartition strictly. However, by loosening the balancing constraint, the spectral bisection can identify clusters efficiently. We propose a k-way graph partitioning algorithm based on clustering using recursive spectral bisection. After a graph is divided into a partition, the partition is adjusted in order to meet the balancing constraint. Experimental results show that the clustering based k-way partitioning generates partitions with 83.8 similar to 108.4% cutsets compared to the strict recursive spectral bisections or multi-level partitions.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/17876
- DOI
- 10.1007/978-3-540-24687-9_81
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- LECTURE NOTES IN COMPUTER SCIENCE, vol. 3037, page. 598 - 601, 2004-01
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.