Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/62140
Title: A distributed algorithm for graph sparsification
Authors: Li, Chunming
Keywords: DRNTU::Science::Physics
Issue Date: 2015
Source: Li, C. (2015). A distributed algorithm for graph sparsification. Master's thesis, Nanyang Technological University, Singapore.
Abstract: 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).
URI: http://hdl.handle.net/10356/62140
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
Li Chunming.pdf
  Restricted Access
248.18 kBAdobe PDFView/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.