Name
Abstract | ||
|---|---|---|
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 p in the total coverage area, there exist a color i and a region D such that p@?D, the region D is colored i, and every other region D^' that contains p is not colored i. 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) approximation algorithm for the conflict-free coloring problem where the regions are unit disks. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.dam.2008.09.005 | Discrete Applied Mathematics |
Keywords | Field | DocType |
conflict-free colorings,unit disk graphs,siam j. comput,region d,wireless networks,conflict-free coloring problem,point p,simple geometric region,unit disk,s. smorodinsky,geometric conflict-free,frequency assignment,color i,conflict-free coloring,unit disk graph,wireless network,cellular network | Wireless network,Approximation algorithm,Discrete mathematics,Complete coloring,Colored,Radio networks,Combinatorics,Cellular network,Frequency assignment,Mathematics,Coloring problem | Journal |
Volume | Issue | ISSN |
157 | 7 | Discrete Applied Mathematics |
Citations | PageRank | References |
6 | 0.49 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nissan Lev-Tov | 1 | 137 | 7.91 |
| David Peleg | 2 | 6662 | 824.19 |