תקציר
A partition (C1,C2,...,Cq) of G = (V,E) into clusters of strong (respectively, weak) diameter d, such that the supergraph obtained by contracting each Ci is ℓ-colorable is called a strong (resp., weak) (d, ℓ)-network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong network-decompositions can be computed in distributed deterministic time. Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O(1). However, the parameter ℓ in his result is O(n1/2 + ε). In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong (O(1), O(nε))-network-decompositions. As a corollary we derive a constant-time randomized O(nε)-approximation algorithm for the distributed minimum coloring problem. This improves the best previously-known O(n1/2 + ε) approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic -time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open problem of Lenzen and Wattenhofer (2010).
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | Structural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, Post-Proceedings |
עורכים | Christian Scheideler |
מוציא לאור | Springer Verlag |
עמודים | 209-223 |
מספר עמודים | 15 |
מסת"ב (מודפס) | 9783319252575 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 2015 |
אירוע | 22nd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2015 - Montserrat, ספרד משך הזמן: 14 יולי 2015 → 16 יולי 2015 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 9439 |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 22nd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2015 |
---|---|
מדינה/אזור | ספרד |
עיר | Montserrat |
תקופה | 14/07/15 → 16/07/15 |
הערה ביבליוגרפית
Publisher Copyright:© Springer International Publishing Switzerland 2015.