On the optimality of the median cut spectral bisection graph partitioning method

T.F. Chan, P. Ciarlet Jr., W.K. Szeto

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

Recursive spectral bisection (RSB) is a heuristic technique for finding a minimum cut graph bisection. To use this method the second eigenvector of the Laplacian of the graph is computed and from it a bisection is obtained. The most common method is to use the median of the components of the second eigenvector to induce a bisection. We prove here that this median cut method is optimal in the sense that the partition vector induced by it is the closest partition vector, in any ls norm, for s > 1, to the second eigenvector. Moreover, we prove that the same result also holds for any m-partition, that is, a partition into m and (n - m) vertices, when using the mth largest or smallest components of the second eigenvector.
Original languageEnglish
Pages (from-to)943-948
Number of pages6
JournalSIAM Journal of Scientific Computing
Volume18
Issue number3
DOIs
StatePublished - 1997
Externally publishedYes

Keywords

  • Eigenvectors
  • Fiedler vector
  • Graph Laplacian
  • Graph partitioning method
  • Recursive spectral bisection, Eigenvalues and eigenfunctions
  • Heuristic methods
  • Parallel processing systems
  • Recursive functions
  • Vectors, Graph theory

Fingerprint

Dive into the research topics of 'On the optimality of the median cut spectral bisection graph partitioning method'. Together they form a unique fingerprint.

Cite this