Spectral Sparsification of Graphs

Details Spectral Sparsification of Graphs Spectral Sparsification of Graphs

2008-08-29

arxiv.org/abs/0808.4134v3

Computer Science

Data Structures and Algorithms

This revision addresses comments of the referees. In particular, we have completely re-written the proof of the main graph par

Scientific paper

We introduce a new notion of graph sparsificaiton based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time $\softO{m}$, where $m$ is the number of edges in the original graph. This construction is a key component of a nearly-linear time algorithm for solving linear equations in diagonally-dominant matrcies. Our sparsification algorithm makes use of a nearly-linear time algorithm for graph partitioning that satisfies a strong guarantee: if the partition it outputs is very unbalanced, then the larger part is contained in a subgraph of high conductance.

Affiliated with

Also associated with

No associations

Rating

Spectral Sparsification of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spectral Sparsification of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectral Sparsification of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544333