2015/02/09 by Fabian Fuchs, Fabian B. Fuchs, Fuchs, Fabian +2
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.1502.02426
arxiv created 2015/02/09 · openalex publication_date 2015/02/09 · arxiv updated 2015/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In wireless ad hoc or sensor networks, distributed node coloring is a fundamental problem closely related to establishing efficient communication through TDMA schedules. For networks with maximum degree Delta, a Delta + 1 coloring is the ultimate goal in the distributed setting as this is always possible. In this work we propose Delta + 1 coloring algorithms for the synchronous and asynchronous setting. All algorithms have a runtime of O(Delta log n) time slots. This improves on the previous algorithms for the SINR model either in terms of the number of required colors or the runtime and matches the runtime of local broadcasting in the SINR model (which can be seen as a lower bound).