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
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- The ellipsoid method and its consequences in combinatorial optimization
- Some simplified NP-complete graph problems
- Lower Bounds for the Partitioning of Graphs
- The eigenvalues of random symmetric matrices
- Graph bisection algorithms with good average case behavior
- A framework for solving VLSI graph layout problems
- On the second eigenvalue of random regular graphs
- Fast solution of some random NP-hard problems