%0 Journal Article %1 Spielman1996 %A Spielman, Daniel A. %A Teng, Shang-Hua %D 1996 %K clustering article algorithm machinelearning %T Spectral Partitioning Works: Planar Graphs and Finite Element Meshes %U citeseer.ist.psu.edu/article/spielman96spectral.html %X Spectral partitioning methods use the Fiedler vector|the eigenvector of the second- smallest eigenvalue of the Laplacian matrix|to nd a small separator of a graph. These methods are important components of many scienti c numerical algorithms and have been demonstrated by experiment to work extremely well. In this paper, we show that spectral partitioning methods work well on bounded-degree planar graphs and nite element meshes| the classes of graphs to which they are usually applied. While naive spectral bisection does not necessarily work, we prove that spectral partitioning techniques can be used to produce p separators whose ratio of vertices removed to edges cut is O( n) for bounded-degree planar graphs and two-dimensional meshes and O n1=d for well-shaped d-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs.

@article{Spielman1996, abstract = { Spectral partitioning methods use the Fiedler vector|the eigenvector of the second- smallest eigenvalue of the Laplacian matrix|to nd a small separator of a graph. These methods are important components of many scienti c numerical algorithms and have been demonstrated by experiment to work extremely well. In this paper, we show that spectral partitioning methods work well on bounded-degree planar graphs and nite element meshes| the classes of graphs to which they are usually applied. While naive spectral bisection does not necessarily work, we prove that spectral partitioning techniques can be used to produce p separators whose ratio of vertices removed to edges cut is O( n) for bounded-degree planar graphs and two-dimensional meshes and O n1=d for well-shaped d-dimensional meshes. The heart of our analysis is an upper bound on the second-smallest eigenvalues of the Laplacian matrices of these graphs. }, added-at = {2007-02-19T15:45:18.000+0100}, author = {Spielman, Daniel A. and Teng, Shang-Hua}, biburl = {https://www.bibsonomy.org/bibtex/2fbfcc8edfe30084377aa2cd78ad0eede/tmalsburg}, description = {diese Referenz mag nicht 100%ig stimmen}, interhash = {83f3d15605beda920551830ccac3d79a}, intrahash = {fbfcc8edfe30084377aa2cd78ad0eede}, keywords = {clustering article algorithm machinelearning}, timestamp = {2007-02-19T15:45:18.000+0100}, title = {Spectral Partitioning Works: Planar Graphs and Finite Element Meshes}, url = {citeseer.ist.psu.edu/article/spielman96spectral.html}, year = 1996 }