Improvements on spectral bisection

MaRDI QIDQ4989699zbMATHFDO

Authors Israel de Souza Rocha

Publication date 26 May 2021

Full work available at URL https://arxiv.org/abs/1703.00268

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph partitioninggraph bisectionspectral partitioning

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18) Combinatorial optimization (90C27) Semidefinite programming (90C22) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

• Spectral bisection with two eigenvectors
• Spectral partitioning works: planar graphs and finite element meshes
• Publication:4886053
• On the Quality of Spectral Separators
• On the Optimality of the Median Cut Spectral Bisection Graph Partitioning Method

Cites work

• 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?)
• 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
• 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 II
• The Laplacian spectrum of a graph
• The third smallest eigenvalue of the Laplacian matrix

Cited in

(4)

• Ranks and representations for spectral graph bisection
• Spectral bisection with two eigenvectors
• Improved parameter identification using additional spectral information
• scientific article; zbMATH DE number 741209 (Why is no real title available?)

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)