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...

Full description

Saved in:
Bibliographic Details
Main Author: Li, Chunming
Other Authors: Gopal Pandurangan
Format: Theses and Dissertations
Language:English
Published: 2015
Subjects:
Online Access:http://hdl.handle.net/10356/62140
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-62140
record_format dspace
spelling sg-ntu-dr.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
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Physics
spellingShingle DRNTU::Science::Physics
Li, Chunming
A distributed algorithm for graph sparsification
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).
author2 Gopal Pandurangan
author_facet Gopal Pandurangan
Li, Chunming
format Theses and Dissertations
author Li, Chunming
author_sort Li, Chunming
title A distributed algorithm for graph sparsification
title_short 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_sort distributed algorithm for graph sparsification
publishDate 2015
url http://hdl.handle.net/10356/62140
_version_ 1759855510055550976