کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418821 | 681720 | 2009 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Conflict-free coloring of unit disks Conflict-free coloring of unit disks](/preview/png/418821.png)
The paper considers the geometric conflict-free coloring problem, introduced in [G. Even, Z. Lotker, D. Ron, S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM J. Comput. 33 (2003) 94–133]. The input of this problem is a set of regions in the plane and the output is an assignment of colors to the regions, such that for every point pp in the total coverage area, there exist a color ii and a region DD such that p∈Dp∈D, the region DD is colored ii, and every other region D′D′ that contains pp is not colored ii. The target is to minimize the number of colors used. This problem arises from issues of frequency assignment in radio networks. The paper presents an O(1)O(1) approximation algorithm for the conflict-free coloring problem where the regions are unit disks.
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1521–1532