Back to University of Twente portal
A conjugate gradient method for the spectral partitioning of graphs
Kruyt, N.P. (1997) A conjugate gradient method for the spectral partitioning of graphs. Parallel Computing, 22 (11). pp. 1493-1502. ISSN 0167-8191
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 615Kb |
| Abstract: | The partitioning of graphs is a frequently occurring problem in science and engineering. The spectral graph partitioning method is a promising heuristic method for this class of problems. Its main disadvantage is the large computing time required to solve a special eigenproblem. Here a simple and efficient method is proposed to reduce this computing time. This method is based on the conjugate gradient minimization method. The convergence properties of the new method are studied for the case of regular one-, two-, and three-dimensional grids. The influence of the aspect ratio of the graph on the convergence rate is also investigated. |
| Item Type: | Article |
| Copyright: | © 1997 Elsevier Science |
| Faculty: | Engineering Technology (CTW) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/57232 |
| Official URL: | http://dx.doi.org/10.1016/S0167-8191(96)00059-2 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page