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.
%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
}