Eigenvalues and graph bisection: An average-case analysis
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 280-285
- https://doi.org/10.1109/sfcs.1987.22
Abstract
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.Keywords
This publication has 9 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- On the second eigenvalue of random regular graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987
- Fast solution of some random NP-hard problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- The eigenvalues of random symmetric matricesCombinatorica, 1981
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- Lower Bounds for the Partitioning of GraphsIBM Journal of Research and Development, 1973
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952