Improvements On Spectral Bisection

0539510 - ÚI 2021 RIV IL eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: Graph partitioning * Graph bisection * Spectral Partitioning
Obor OECD: Pure mathematics
Impakt faktor: 0.682, rok: 2020
Způsob publikování: 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.
Trvalý link: http://hdl.handle.net/11104/0317243