Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18) Integer programming (90C10) Semidefinite programming (90C22) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)
Abstract: We investigate combinatorial properties of certain configurations of a graph partition which are related to the minimality of a cut. We show that such configurations are related to the third eigenvector of the Laplacian matrix. It is well known that the second eigenvector encodes structural information, and that can be used to approximate a minimum bisection. In this paper, we show that the third eigenvector carries structural information as well. We then provide a new spectral bisection algorithm using both eigenvectors. The new algorithm is guaranteed to return a cut that is smaller or equal to the one returned by the classic spectral bisection. Also, we provide a spectral algorithm that can refine a given partition and produce a smaller cut.
Recommendations
Cites work
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- Finding good approximate vertex and edge partitions is NP-hard
- scientific article; zbMATH DE number 3681933 (Why is no real title available?)
- scientific article; zbMATH DE number 867649 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Isoperimetric Partitioning: A New Algorithm for Graph Partitioning
- Lower Bounds for the Partitioning of Graphs
- On the Quality of Spectral Separators
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- Some Modified Matrix Eigenvalue Problems
- Spectral partitioning works: planar graphs and finite element meshes
- The Laplacian spectrum of a graph
- The Laplacian Spectrum of a Graph II
- The third smallest eigenvalue of the Laplacian matrix
Cited in
(5)- Spectral bisection with two eigenvectors
- Improved parameter identification using additional spectral information
- Ranks and representations for spectral graph bisection
- scientific article; zbMATH DE number 741209 (Why is no real title available?)
- On the Optimality of the Median Cut Spectral Bisection Graph Partitioning Method
This page was built for publication: Improvements on spectral bisection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989699)
