Titre : On the optimality of the median cut spectral bisection graph partitioning method
Année : 1997
Type : article_acl
Auteurs : T. Chan, P. Ciarlet, W. Szeto
Résumé : 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\ge1$, 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. Copyright © 1997 Society for Industrial and Applied Mathematics
Thèmes :
Référence : SIAM Journal on Scientific Computing - vol. 18(3) (pp 943-948 )