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

Tony F. Chan Patrick Ciarlet 1 W. K. Szeto
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
Document type :
Journal articles
Complete list of metadatas

https://hal-ensta-paris.archives-ouvertes.fr//hal-01010396
Contributor : Aurélien Arnoux <>
Submitted on : Thursday, June 19, 2014 - 4:22:15 PM
Last modification on : Thursday, July 4, 2019 - 4:00:49 AM

Identifiers

Collections

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⟩

Share

Metrics

Record views

191