Improvements On Spectral Bisection

0539510 - ÚI 2021 RIV IL eng J - Journal Article
Rocha, Israel
Improvements On Spectral Bisection.
Electronic Journal of Linear Algebra. Roč. 36, December (2020), s. 857-877. ISSN 1537-9582. E-ISSN 1081-3810
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : Graph partitioning * Graph bisection * Spectral Partitioning
OECD category: Pure mathematics
Impact factor: 0.682, year: 2020
Method of publishing: Open access

In this paper, the third eigenvalue of the Laplacian matrix is used to provide a lower bound on the minimum cutsize. This result has algorithmic implications that are exploited in this paper. Besides, combinatorial properties of certain configurations of a graph partition which are related to the minimality of a cut are investigated. It is shown 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, it is shown that the third eigenvector carries structural information as well. Then a new spectral bisection algorithm using both eigenvectors is provided. The new algorithm is guaranteed to return a cut that is smaller or equal to the one returned by the classic spectral bisection. Also, a spectral algorithm that can refine a given partition and produce a smaller cut is provided.
Permanent Link: http://hdl.handle.net/11104/0317243