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

1 POEMS - Propagation des Ondes : Étude Mathématique et Simulation
Inria Saclay - Ile de France, UMA - Unité de Mathématiques Appliquées, CNRS - Centre National de la Recherche Scientifique : UMR7231
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\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
Type de document :
Article dans une revue
SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 1997, 18 (3), pp.943-948. 〈10.1137/S1064827594262649〉

https://hal-ensta.archives-ouvertes.fr/hal-01010396
Contributeur : Aurélien Arnoux <>
Soumis le : jeudi 19 juin 2014 - 16:22:15
Dernière modification le : jeudi 11 janvier 2018 - 06:20:23

### Citation

Tony F. Chan, Patrick Ciarlet, W. K. Szeto. On the optimality of the median cut spectral bisection graph partitioning method. SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 1997, 18 (3), pp.943-948. 〈10.1137/S1064827594262649〉. 〈hal-01010396〉

### Métriques

Consultations de la notice