%0 Journal Article
%T On the optimality of the median cut spectral bisection graph partitioning method
%+ Propagation des Ondes : Étude Mathématique et Simulation (POEMS)
%A Chan, Tony F.
%A Ciarlet, Patrick
%A Szeto, W. K.
%< avec comité de lecture
%@ 1064-8275
%J SIAM Journal on Scientific Computing
%I Society for Industrial and Applied Mathematics
%V 18
%N 3
%P 943-948
%8 1997
%D 1997
%R 10.1137/S1064827594262649Journal articles
%X 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
%G English
%L hal-01010396
%U https://hal-ensta-paris.archives-ouvertes.fr//hal-01010396
%~ ENSTA
%~ CNRS
%~ INRIA
%~ UMA_ENSTA
%~ INRIA-SACLAY
%~ INRIA_TEST
%~ INRIA2