TY - JOUR
T1 - Local algorithms for edge colorings in UDGs
AU - Kanj, Iyad A.
AU - Wiese, Andreas
AU - Zhang, Fenghui
N1 - Funding Information:
The first author was supported in part by a DePaul University Competitive Research Grant.
PY - 2011/8/12
Y1 - 2011/8/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79960559652&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2011.05.005
DO - 10.1016/j.tcs.2011.05.005
M3 - Article
AN - SCOPUS:79960559652
SN - 0304-3975
VL - 412
SP - 4704
EP - 4714
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 35
ER -