Locally-iterative distributed (+1)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
From MaRDI portal
(Redirected from Publication:5197709)
Locally-iterative distributed \((\Delta+1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
Locally-iterative distributed \((\Delta+1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
Abstract: We consider graph coloring and related problems in the distributed message-passing model. {Locally-iterative algorithms} are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its 1-hop neighborhood. In STOC'93 Szegedy and Vishwanathan showed that any locally-iterative (Delta+1)-coloring algorithm requires Omega(Delta log Delta + log^* n) rounds, unless there is "a very special type of coloring that can be very efficiently reduced" cite{SV93}. In this paper we obtain this special type of coloring. Specifically, we devise a locally-iterative (Delta+1)-coloring algorithm with running time O(Delta + log^* n), i.e., {below} Szegedy-Vishwanathan barrier. This demonstrates that this barrier is not an inherent limitation for locally-iterative algorithms. As a result, we also achieve significant improvements for dynamic, self-stabilizing and bandwidth-restricted settings: - We obtain self-stabilizing distributed algorithms for (Delta+1)-vertex-coloring, (2Delta-1)-edge-coloring, maximal independent set and maximal matching with O(Delta+log^* n) time. This significantly improves previously-known results that have O(n) or larger running times cite{GK10}. - We devise a (2Delta-1)-edge-coloring algorithm in the CONGEST model with O(Delta + log^* n) time and in the Bit-Round model with O(Delta + log n) time. Previously-known algorithms had superlinear dependency on Delta for (2Delta-1)-edge-coloring in these models. - We obtain an arbdefective coloring algorithm with running time O(sqrt Delta + log^* n). We employ it in order to compute proper colorings that improve the recent state-of-the-art bounds of Barenboim from PODC'15 cite{B15} and Fraigniaud et al. from FOCS'16 cite{FHK16} by polylogarithmic factors. - Our algorithms are applicable to the SET-LOCAL model of cite{HKMS15}.
Recommendations
- Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
- Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
- (2-1)-edge-coloring is much easier than maximal matching in the distributed setting
Cited in
(16)- Improved distributed \(\Delta\)-coloring
- Linial for lists
- Distributed reconfiguration of maximal independent sets
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Locally-iterative Distributed (Δ + 1)-coloring and Applications
- Distributed Reconfiguration of Maximal Independent Sets
- Distributed arboricity-dependent graph coloring via all-to-all communication
- Distributed (+1)-coloring via ultrafast graph shattering
- A topological perspective on distributed network algorithms
- Local conflict coloring revisited: Linial for lists
- Coloring fast without learning your neighbors' colors
- Distributed computing in the asynchronous LOCAL model
- Fast deterministic algorithms for highly-dynamic networks
- Local distributed rounding: generalized to MIS, matching, set cover, and beyond
- Distributed edge coloring in time polylogarithmic in \({\Delta }\)
This page was built for publication: Locally-iterative distributed \((\Delta+1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197709)
