Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

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)