2017/03/01 by Israel Rocha, Rocha, Israel
Computer Science · Engineering · #05C85 #15A18 #90C10 #90C22 #90C27 #90C35 #Combinatorics (math.CO) #Embedded Systems Design Techniques #FOS: Mathematics #VLSI and Analog Circuit Testing #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1703.00268
openalex publication_date 2017/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.