Improvements on spectral bisection

zbMATH Open1464.05306arXiv1703.00268MaRDI QIDQ4989699FDOQ4989699

Authors: Israel de Souza Rocha 

Publication date: 26 May 2021

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.

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

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

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

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)

Cites Work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Title not available (Why is that?)
• The Laplacian Spectrum of a Graph II
• Finding good approximate vertex and edge partitions is NP-hard
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Title not available (Why is that?)
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Title not available (Why is that?)
• Some Modified Matrix Eigenvalue Problems
• Lower Bounds for the Partitioning of Graphs
• Spectral partitioning works: planar graphs and finite element meshes
• The Laplacian spectrum of a graph
• On the Quality of Spectral Separators
• Multi-way spectral partitioning and higher-order Cheeger inequalities
• The third smallest eigenvalue of the Laplacian matrix
• Isoperimetric Partitioning: A New Algorithm for Graph Partitioning

Cited In (4)

• Ranks and representations for spectral graph bisection
• Spectral bisection with two eigenvectors
• Improved parameter identification using additional spectral information
• Title not available (Why is that?)

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)