Spectral partitioning of random graphs
Top Cited Papers
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 529-537
- https://doi.org/10.1109/sfcs.2001.959929
Abstract
Problems such as bisection, graph coloring, and clique are generally believed hard in the worst case. However, they can be solved if the input data is drawn randomly from a distribution over graphs containing acceptable solutions. In this paper we show that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density. In nearly all cases our approach meets or exceeds previous parameters, while introducing substantial generality. We apply spectral techniques, using foremost the observation that in all of these problems, the expected adjacency matrix is a low rank matrix wherein the structure of the solution is evident.Keywords
This publication has 15 references indexed in Scilit:
- Simulated annealing for graph bisectionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On clusterings-good, bad and spectralPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fast computation of low rank matrix approximationsPublished by Association for Computing Machinery (ACM) ,2001
- Algorithms for graph partitioning on the planted partition modelRandom Structures & Algorithms, 2001
- Algorithms for Graph Partitioning on the Planted Partition ModelPublished by Springer Nature ,1999
- A Spectral Technique for Coloring Random 3-Colorable GraphsSIAM Journal on Computing, 1997
- Coloring Random and Semi-Random k-Colorable GraphsJournal of Algorithms, 1995
- Almost all k-colorable graphs are easy to colorJournal of Algorithms, 1988
- Expected behavior of graph coloring algorithmsLecture Notes in Computer Science, 1977
- The Rotation of Eigenvectors by a Perturbation. IIISIAM Journal on Numerical Analysis, 1970