Local algorithms for edge colorings in UDGs

Iyad A. Kanj, Andreas Wiese, Fenghui Zhang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In this paper, we consider two problems: the edge coloring and the strong edge coloring problems on unit disk graphs (UDGs). Both problems have important applications in wireless sensor networks as they can be used to model link scheduling problems in such networks. It is well known that both problems are NP-complete, and approximation algorithms for them have been extensively studied under the centralized model of computation. Centralized algorithms, however, are not suitable for ad hoc wireless sensor networks whose devices typically have limited resources, and lack the centralized coordination. We develop local distributed approximation algorithms for the edge coloring and the strong edge coloring problems on unit disk graphs. For the edge coloring problem, our local distributed algorithm has approximation ratio 2 and locality 50. For the strong edge coloring problem on UDGs, we present two local distributed algorithms with different tradeoffs between their approximation ratio and locality. The first algorithm has ratio 128 and locality 22, whereas the second algorithm has ratio 10 and locality 180.

Original languageEnglish
Pages (from-to)4704-4714
Number of pages11
JournalTheoretical Computer Science
Volume412
Issue number35
DOIs
StatePublished - 12 Aug 2011
Externally publishedYes

Fingerprint

Dive into the research topics of 'Local algorithms for edge colorings in UDGs'. Together they form a unique fingerprint.

Cite this