Reference
Schneider, J., & Wattenhofer, R. (2009). Coloring Unstructured Multi-Hop Networks. Paper presented at the Principles of Distributed Computing (PODC).
Publication type
Paper in Conference Proceedings
Abstract
We present a randomized coloring algorithm for the unstructured radio network model, a model comprising autonomous nodes, asynchronous wake-up, no collision detection and an unknown but geometric network topology. The current state-of-the-art coloring algorithm needs with high probability O(Delta*log n) time and uses O(Delta) colors, where n and Delta are the number of nodes in the network and the maximum degree, respectively; this algorithm requires knowledge of a linear bound on n and Delta. We improve this result in three ways: Firstly, we improve the time complexity, instead of the logarithmic factor we just need a polylogarithmic additive term ; more speci?cally, our time complexity is O(Delta + log Delta*log n) given an estimate of n and Delta, and O(Delta + log2 n) without knowledge of Delta. Secondly, our vertex coloring algorithm needs Delta + 1 colors only. Thirdly, our algorithm manages to do a distance-d coloring with asymptotically optimal O(Delta) colors for a constant d.
Persons
Organizational Units
- Institute of Information Systems
- Hilti Chair of Business Process Management