DERBEL-2010-351045
Bilel Derbel, Mohamed Mosbah, Akka Zemmari. Sublinear Fully Distributed Partition with Applications. Theory of Computing Systems, 47(3):368-404, 2010.
Download
Download paper:
Follow the link
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Abstract
We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with $n$ nodes into a disjoint set of connected clusters with radius at most $k-1$ and having $O(n^{1+1/k})$ intercluster edges. We show how to implement our algorithms in the distributed $\mathcal{CONGEST}$ model of computation, i.e., limited message size, which improves the time complexity of previous algorithms\ \cite{MS00,Awe85,Peleg00b} from $O(n)$ to $O(n^{1-1/k})$. We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the $\mathcal{CONGEST}$ model
Contact
Bilel Derbel
Mohamed Mosbah
Akka Zemmari
BibTex Reference
@article{DERBEL-2010-351045,
Author = {Derbel, Bilel and Mosbah, Mohamed and Zemmari, Akka},
Title = {Sublinear Fully Distributed Partition with Applications},
Journal = {Theory of Computing Systems},
Volume = {47},
Number = {3},
Pages = {368--404},
Year = {2010}
}
EndNote Reference [help]
Get EndNote Reference (.ref)