A distributed algorithm for graph sparsification
There has been plenty of work on graph cut sparsi cation. Previous works use either combinatorial graph techniques or algebraic graph techniques to obtain the most important parameter in a random sampling process, the probability pe for each edge e. Sampling each edge according to this pe respective...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/62140 |
| _version_ | 1826120714239868928 |
|---|---|
| author | Li, Chunming |
| author2 | Gopal Pandurangan |
| author_facet | Gopal Pandurangan Li, Chunming |
| author_sort | Li, Chunming |
| collection | NTU |
| description | There has been plenty of work on graph cut sparsi cation. Previous works use either combinatorial graph techniques or algebraic graph techniques to obtain the most important parameter in a random sampling process, the probability pe for each edge e. Sampling each edge according to this pe respectively and giving each sampled edge e weight 1/pe yields a good cut sparsi cation of the original graph. This framework has been formalized and su cient conditions for the framework to work have also been developed in the past few years. However prior work has been restricted to centralized setting. Our main contribution is a distributed algorithm for graph sparsification. Our algorithm is designed on simple graphs and also later extended to multi-graphs and weighted graphs. On simple graphs we present an efficient algorithm for finding a skeleton with O(n log2 n2) edges in expectation with running time O(n log2 n). For weighted graphs with polynomial weights, our algorithm takes O(n 1+dlog2 n) time where d is some constant and edge weight is bounded by nd . Our algorithm takes O(nan log n) time for exponential weighted graphs where edge weight is bounded by a n. Our approach uses of random weight minimum spanning tree (RWMST), which is the minimum spanning tree (MST) computed when independently assigning random weight to each edge in the graph. We show an efficient way to approximate edge connectivity using this idea of RWMST and random sampling. Our algorithms are Monte-Carlo, i.e. work with high probability (whp). |
| first_indexed | 2024-10-01T05:21:04Z |
| format | Thesis |
| id | ntu-10356/62140 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:21:04Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | ntu-10356/621402023-02-28T23:45:15Z A distributed algorithm for graph sparsification Li, Chunming Gopal Pandurangan School of Physical and Mathematical Sciences DRNTU::Science::Physics There has been plenty of work on graph cut sparsi cation. Previous works use either combinatorial graph techniques or algebraic graph techniques to obtain the most important parameter in a random sampling process, the probability pe for each edge e. Sampling each edge according to this pe respectively and giving each sampled edge e weight 1/pe yields a good cut sparsi cation of the original graph. This framework has been formalized and su cient conditions for the framework to work have also been developed in the past few years. However prior work has been restricted to centralized setting. Our main contribution is a distributed algorithm for graph sparsification. Our algorithm is designed on simple graphs and also later extended to multi-graphs and weighted graphs. On simple graphs we present an efficient algorithm for finding a skeleton with O(n log2 n2) edges in expectation with running time O(n log2 n). For weighted graphs with polynomial weights, our algorithm takes O(n 1+dlog2 n) time where d is some constant and edge weight is bounded by nd . Our algorithm takes O(nan log n) time for exponential weighted graphs where edge weight is bounded by a n. Our approach uses of random weight minimum spanning tree (RWMST), which is the minimum spanning tree (MST) computed when independently assigning random weight to each edge in the graph. We show an efficient way to approximate edge connectivity using this idea of RWMST and random sampling. Our algorithms are Monte-Carlo, i.e. work with high probability (whp). Master of Science 2015-01-21T08:14:51Z 2015-01-21T08:14:51Z 2015 2015 Thesis Li, C. (2015). A distributed algorithm for graph sparsification. Master's thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/62140 en 41 p. application/pdf |
| spellingShingle | DRNTU::Science::Physics Li, Chunming A distributed algorithm for graph sparsification |
| title | A distributed algorithm for graph sparsification |
| title_full | A distributed algorithm for graph sparsification |
| title_fullStr | A distributed algorithm for graph sparsification |
| title_full_unstemmed | A distributed algorithm for graph sparsification |
| title_short | A distributed algorithm for graph sparsification |
| title_sort | distributed algorithm for graph sparsification |
| topic | DRNTU::Science::Physics |
| url | http://hdl.handle.net/10356/62140 |
| work_keys_str_mv | AT lichunming adistributedalgorithmforgraphsparsification AT lichunming distributedalgorithmforgraphsparsification |