Eigenvalues and graph bisection: An average-case analysis

Ravi B. Boppana · Annual Symposium on Foundations of Computer Science · 1987

Graph Bisection is the problem of partitioning the vertices of a graph into two equal-size pieces so as to minimize the number of edges between the two pieces. This paper presents an algorithm that will, for almost all graphs in a certain class, output the minimum-size bisection. Furthermore the algorithm will yield, for almost all such graphs, a proof that the bisection is optimal. The algorithm is based on computing eigenvalues and eigenvectors of matrices associated with the graph.

Cited by 318 works. doi:10.1109/sfcs.1987.22

Authors

References